結果

問題 No.3016 ハチマキおじさん
ユーザー GOTKAKO
提出日時 2025-01-25 13:27:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 57 ms / 2,000 ms
コード長 1,349 bytes
コンパイル時間 2,324 ms
コンパイル使用メモリ 203,460 KB
実行使用メモリ 10,904 KB
最終ジャッジ日時 2025-01-25 22:47:42
合計ジャッジ時間 5,166 ms
ジャッジサーバーID
（参考情報） 		judge8 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

    int N; cin >> N;
    vector<int> apA(N),apB(N);
    for(int t=0; t<N; t++){
        int a; cin >> a; a--;
        apA.at(a)++;
    }
    for(int t=0; t<N-1; t++){
        int a; cin >> a; a--;
        apB.at(a)++;
    }

    vector<int> A,B;
    for(int i=0; i<N; i++){
        int del = min(apA.at(i),apB.at(i));
        apA.at(i) -= del; apB.at(i) -= del;
        while(apA.at(i)--) A.push_back(i);
        while(apB.at(i)--) B.push_back(i);
    }

    int n = B.size();
    vector<long long> L(n),R(n);
    long long sum = 0;
    for(int i=0; i<n; i++){
        sum += abs(B.at(i)-A.at(i));
        L.at(i) = sum; 
    }
    sum = 0;
    for(int i=n-1; i>=0; i--){
        sum += abs(B.at(i)-A.at(i+1));
        R.at(i) = sum;
    }
    long long best = 1e18;
    vector<int> answer;
    for(int i=0; i<=n; i++){
        long long l = 0,r = 0;
        if(i) l = L.at(i-1);
        if(i != n) r = R.at(i);
        if(l+r < best) best = l+r,answer = {A.at(i)};
        else if(l+r == best) answer.push_back(A.at(i)); 
    }
    answer.erase(unique(answer.begin(),answer.end()),answer.end());
    cout << answer.size() << endl;
    for(int i=0; i<answer.size(); i++) cout << answer.at(i)+1 << (i==answer.size()-1?"\n":" ");
}
0