C. Pearls in a Row ～貪欲＋コーナーケースという罠～

1500
  • Quiz
  • AC
  • 感想
    • 解法は貪欲でOK。サンプルケースは全て通るので提出！WA
    • 全てのPearlはそれぞれ1度、範囲に含まれている必要がある
    • A = [1,1,1,1,2]のときは、答えは(1,2), (3,5)とする必要がある
    • 「んー貪欲しか思いつかないし、貪欲で正しい気がする。投げちゃえ！」をはめるコーナーケースには注意
    • 貪欲を投げる前は考慮漏れがないか、いつもより注意しよう
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];
    
    map<ll,ll> mp;

    ll left=0;
    vector<PII> Ans;
    rep(i,N){
      ll a = A[i];
      mp[a]++;
      if(mp[a]>=2){
        Ans.push_back({left,i});
        mp.clear();
        left=i+1;
      }
    }
    if(SZ(Ans)==0){
      p(-1);return 0;
    }else{
      Ans.back().second=N-1;
    }

    p(SZ(Ans));
    for(auto pa : Ans){
      p2(pa.first+1, pa.second+1);
    }
    
    return 0;
}