結果

問題 No.366 ロボットソート
コンテスト
ユーザー Tiến Mạnh Trần
提出日時 2026-02-10 17:37:16
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,550 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,525 ms
コンパイル使用メモリ 227,736 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2026-02-10 17:37:20
合計ジャッジ時間 3,591 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

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

    int N, W;
    cin >> N >> W;
    vector<int> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];

    vector<int> sorted = A;
    sort(sorted.begin(), sorted.end());

    vector<int> pos(N);
    for(int i = 0; i < N; i++) pos[i] = i;

    vector<bool> used(N, false);
    int ans = 0;

    for(int start = 0; start < N; start++){
        if(used[start]) continue;

        // build component
        vector<int> comp;
        for(int i = start; i < N; i += W){
            comp.push_back(i);
            used[i] = true;
        }

        // values in component
        vector<int> cur, need;
        for(int i : comp){
            cur.push_back(A[i]);
            need.push_back(sorted[i]);
        }

        sort(cur.begin(), cur.end());
        sort(need.begin(), need.end());

        if(cur != need){
            cout << -1 << '\n';
            return 0;
        }

        // mapping value -> index
        unordered_map<int,int> mp;
        for(int i = 0; i < (int)comp.size(); i++){
            mp[A[comp[i]]] = i;
        }

        vector<bool> vis(comp.size(), false);
        for(int i = 0; i < (int)comp.size(); i++){
            if(vis[i]) continue;
            int len = 0, curi = i;
            while(!vis[curi]){
                vis[curi] = true;
                curi = mp[ sorted[ comp[curi] ] ];
                len++;
            }
            ans += max(0, len - 1);
        }
    }

    cout << ans << '\n';
}
0