提出 #74357141

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
int n, k, a[200010];
int b[200010];
void work(){
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)cin >> a[i];
    static int p[200010];
    int tp = 0, ct = 0;
    static int bt[200010];
    fill_n(bt + 1, n, 0);
    for (int i = 1; i <= n; ++i)if (!bt[i]){
        ++ct;
        for (int u = i; !bt[u]; u = a[u])p[++tp] = u, bt[u] = ct;
    }
    ct += n;
    if (k > ct || (k & 1) != (ct & 1)){
        cout << "No" << "\n";
        return;
    }
    iota(b + 1, b + n + 1, 1);
    for (int i = 2, ls = 0; i <= n && ct > k; ++i){
        if (bt[p[i - 1]] != bt[p[i]])swap(b[p[1]], b[p[i]]), ct -= 2;
        else if (ls)swap(b[ls], b[p[i]]), ls = 0, ct -= 2;
        else ls = p[i], swap(b[p[1]], b[p[i]]);
    }
    cout << "Yes" << "\n";
    for (int i = 1; i <= n; ++i)cout << b[i] << " ";
    cout << "\n";
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)work();
    return 0;
}

提出情報

提出日時
問題 E - Number of Cycles
ユーザ szt100309
言語 C++23 (GCC 15.2.0)
得点 1400
コード長 1029 Byte
結果 AC
実行時間 21 ms
メモリ 6908 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 1400 / 1400
結果
AC × 1
AC × 82
セット名 テストケース
Sample 00-sample-001.txt
All 00-sample-001.txt, 01-001.txt, 01-002.txt, 01-003.txt, 01-004.txt, 01-005.txt, 01-006.txt, 01-007.txt, 01-008.txt, 01-009.txt, 01-010.txt, 01-011.txt, 01-012.txt, 01-013.txt, 01-014.txt, 01-015.txt, 01-016.txt, 01-017.txt, 01-018.txt, 01-019.txt, 01-020.txt, 01-021.txt, 01-022.txt, 01-023.txt, 01-024.txt, 01-025.txt, 01-026.txt, 01-027.txt, 01-028.txt, 01-029.txt, 01-030.txt, 01-031.txt, 01-032.txt, 01-033.txt, 01-034.txt, 01-035.txt, 01-036.txt, 01-037.txt, 01-038.txt, 01-039.txt, 01-040.txt, 01-041.txt, 01-042.txt, 01-043.txt, 01-044.txt, 01-045.txt, 01-046.txt, 01-047.txt, 01-048.txt, 01-049.txt, 01-050.txt, 01-051.txt, 01-052.txt, 01-053.txt, 01-054.txt, 01-055.txt, 01-056.txt, 01-057.txt, 01-058.txt, 01-059.txt, 01-060.txt, 01-061.txt, 01-062.txt, 01-063.txt, 01-064.txt, 01-065.txt, 01-066.txt, 01-067.txt, 01-068.txt, 01-069.txt, 01-070.txt, 01-071.txt, 01-072.txt, 01-073.txt, 01-074.txt, 01-075.txt, 01-076.txt, 01-077.txt, 01-078.txt, 01-079.txt, 01-080.txt, 01-081.txt
ケース名 結果 実行時間 メモリ
00-sample-001.txt AC 1 ms 3676 KiB
01-001.txt AC 10 ms 3680 KiB
01-002.txt AC 10 ms 3676 KiB
01-003.txt AC 6 ms 3676 KiB
01-004.txt AC 12 ms 3904 KiB
01-005.txt AC 16 ms 3936 KiB
01-006.txt AC 10 ms 3724 KiB
01-007.txt AC 15 ms 3560 KiB
01-008.txt AC 10 ms 3664 KiB
01-009.txt AC 14 ms 3680 KiB
01-010.txt AC 11 ms 3616 KiB
01-011.txt AC 19 ms 3652 KiB
01-012.txt AC 11 ms 6020 KiB
01-013.txt AC 18 ms 6908 KiB
01-014.txt AC 15 ms 6728 KiB
01-015.txt AC 20 ms 6720 KiB
01-016.txt AC 18 ms 6720 KiB
01-017.txt AC 10 ms 5876 KiB
01-018.txt AC 18 ms 6720 KiB
01-019.txt AC 20 ms 6752 KiB
01-020.txt AC 20 ms 6840 KiB
01-021.txt AC 18 ms 6748 KiB
01-022.txt AC 11 ms 5976 KiB
01-023.txt AC 19 ms 6840 KiB
01-024.txt AC 16 ms 6688 KiB
01-025.txt AC 21 ms 6748 KiB
01-026.txt AC 16 ms 6688 KiB
01-027.txt AC 9 ms 5968 KiB
01-028.txt AC 19 ms 6644 KiB
01-029.txt AC 19 ms 6828 KiB
01-030.txt AC 18 ms 6724 KiB
01-031.txt AC 18 ms 6688 KiB
01-032.txt AC 11 ms 6140 KiB
01-033.txt AC 18 ms 6688 KiB
01-034.txt AC 20 ms 6744 KiB
01-035.txt AC 16 ms 6688 KiB
01-036.txt AC 18 ms 6752 KiB
01-037.txt AC 11 ms 5980 KiB
01-038.txt AC 20 ms 6744 KiB
01-039.txt AC 17 ms 6636 KiB
01-040.txt AC 20 ms 6748 KiB
01-041.txt AC 15 ms 6744 KiB
01-042.txt AC 11 ms 5900 KiB
01-043.txt AC 18 ms 6828 KiB
01-044.txt AC 19 ms 6700 KiB
01-045.txt AC 17 ms 6720 KiB
01-046.txt AC 19 ms 6744 KiB
01-047.txt AC 11 ms 5976 KiB
01-048.txt AC 19 ms 6640 KiB
01-049.txt AC 18 ms 6644 KiB
01-050.txt AC 20 ms 6632 KiB
01-051.txt AC 18 ms 6748 KiB
01-052.txt AC 16 ms 6800 KiB
01-053.txt AC 19 ms 6748 KiB
01-054.txt AC 16 ms 6828 KiB
01-055.txt AC 20 ms 6720 KiB
01-056.txt AC 19 ms 6644 KiB
01-057.txt AC 19 ms 6840 KiB
01-058.txt AC 18 ms 6724 KiB
01-059.txt AC 19 ms 6828 KiB
01-060.txt AC 20 ms 6688 KiB
01-061.txt AC 18 ms 6840 KiB
01-062.txt AC 19 ms 6748 KiB
01-063.txt AC 19 ms 6828 KiB
01-064.txt AC 18 ms 6752 KiB
01-065.txt AC 20 ms 6632 KiB
01-066.txt AC 19 ms 6752 KiB
01-067.txt AC 15 ms 6752 KiB
01-068.txt AC 16 ms 6752 KiB
01-069.txt AC 15 ms 6748 KiB
01-070.txt AC 16 ms 6724 KiB
01-071.txt AC 16 ms 6748 KiB
01-072.txt AC 19 ms 6724 KiB
01-073.txt AC 19 ms 6800 KiB
01-074.txt AC 18 ms 6720 KiB
01-075.txt AC 20 ms 6688 KiB
01-076.txt AC 19 ms 6596 KiB
01-077.txt AC 8 ms 5980 KiB
01-078.txt AC 15 ms 6748 KiB
01-079.txt AC 15 ms 6632 KiB
01-080.txt AC 16 ms 6772 KiB
01-081.txt AC 15 ms 6748 KiB