結果

問題 No.2779 Don't make Pair
コンテスト
ユーザー 回転
提出日時 2025-07-30 01:32:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 259 ms / 2,000 ms
コード長 2,220 bytes
コンパイル時間 2,085 ms
コンパイル使用メモリ 206,412 KB
実行使用メモリ 22,304 KB
最終ジャッジ日時 2025-07-30 01:32:17
合計ジャッジ時間 6,968 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
from sortedcontainers import SortedList
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

left = defaultdict(int)
right = defaultdict(int)
for i in A:right[i] += 1
left_count = SortedList([0 for _ in range(N)])
right_count = SortedList(list(right.values()))

ans = []
for i in range(N-1):
    left_count.remove(left[A[i]])
    left_count.add(left[A[i]]+1)
    right_count.remove(right[A[i]])
    right_count.add(right[A[i]]-1)
    left[A[i]] += 1
    right[A[i]] -= 1
    
    if(left_count[-1] <= 1 and right_count[-1] <= 1):
        ans.append(i+1)
print(len(ans))
print(*ans)
*/

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    unordered_map<int,int> left, right;
    for (int x : A) {
        right[x]++;
    }

    // multiset to maintain sorted counts (allows duplicates)
    multiset<int> left_count, right_count;
    // initialize left_count with N zeros
    for (int i = 0; i < N; i++) {
        left_count.insert(0);
    }
    // initialize right_count with the frequencies from 'right'
    for (auto &p : right) {
        right_count.insert(p.second);
    }

    vector<int> ans;
    for (int i = 0; i < N-1; i++) {
        int x = A[i];

        // update left_count: remove old count, insert new count
        {
            auto it = left_count.find(left[x]);
            left_count.erase(it);
            left_count.insert(left[x] + 1);
        }
        // update right_count: remove old count, insert new count
        {
            auto it = right_count.find(right[x]);
            right_count.erase(it);
            right_count.insert(right[x] - 1);
        }

        left[x]++;
        right[x]--;

        // get max of left_count and right_count
        int max_left = *left_count.rbegin();
        int max_right = *right_count.rbegin();

        if (max_left <= 1 && max_right <= 1) {
            ans.push_back(i+1);
        }
    }

    cout << ans.size() << "\n";
    for (int v : ans) {
        cout << v << " ";
    }
    cout << "\n";

    return 0;
}
0