Submission #75823217

Source Code Expand

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;

int n, m;
multiset<int> a;

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);

    cin >> n >> m;
    vector<int> b(m);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a.insert(x);
    }
    for (auto& i : b) cin >> i;
    int idx = 0;
    bool poss = 1;
    vector<int> ans;
    vector<int> pi(m, 0);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j && b[i] != b[j]) j = pi[j - 1];
        if (b[i] == b[j]) pi[i] = ++j;
    }
    while (poss) {
        if (a.count(b[idx])) {
            ans.push_back(b[idx]);
            a.erase(a.find(b[idx]));
            idx++;
            if (idx == m) idx = pi[m - 1];
        } else {
            poss = 0;
            break;
        }
    }
    while (!a.empty()) {
        auto x = begin(a);
        ans.push_back(*x);
        a.erase(x);
    }
    for (auto& i : ans) cout << i << ' ';
}

Submission Info

Submission Time
Task C - Rearrangement
User pluie
Language C++23 (GCC 15.2.0)
Score 100
Code Size 1041 Byte
Status AC
Exec Time 1246 ms
Memory 66336 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 50
Set Name Test Cases
Sample 00-sample-001.txt, 00-sample-002.txt
All 00-sample-001.txt, 00-sample-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
Case Name Status Exec Time Memory
00-sample-001.txt AC 2 ms 3524 KiB
00-sample-002.txt AC 1 ms 3612 KiB
01-003.txt AC 1 ms 3496 KiB
01-004.txt AC 1 ms 3636 KiB
01-005.txt AC 1 ms 3460 KiB
01-006.txt AC 1 ms 3452 KiB
01-007.txt AC 1 ms 3608 KiB
01-008.txt AC 1 ms 3452 KiB
01-009.txt AC 306 ms 55964 KiB
01-010.txt AC 4 ms 4112 KiB
01-011.txt AC 30 ms 9540 KiB
01-012.txt AC 76 ms 13352 KiB
01-013.txt AC 128 ms 18856 KiB
01-014.txt AC 481 ms 57132 KiB
01-015.txt AC 347 ms 54960 KiB
01-016.txt AC 1116 ms 65564 KiB
01-017.txt AC 393 ms 56364 KiB
01-018.txt AC 957 ms 61216 KiB
01-019.txt AC 292 ms 54356 KiB
01-020.txt AC 350 ms 56496 KiB
01-021.txt AC 323 ms 55336 KiB
01-022.txt AC 253 ms 55536 KiB
01-023.txt AC 265 ms 54444 KiB
01-024.txt AC 1027 ms 61212 KiB
01-025.txt AC 228 ms 54528 KiB
01-026.txt AC 332 ms 55464 KiB
01-027.txt AC 284 ms 54520 KiB
01-028.txt AC 318 ms 54764 KiB
01-029.txt AC 305 ms 54460 KiB
01-030.txt AC 252 ms 54476 KiB
01-031.txt AC 1246 ms 66076 KiB
01-032.txt AC 344 ms 55592 KiB
01-033.txt AC 825 ms 59416 KiB
01-034.txt AC 605 ms 66336 KiB
01-035.txt AC 601 ms 66336 KiB
01-036.txt AC 571 ms 66328 KiB
01-037.txt AC 488 ms 59048 KiB
01-038.txt AC 376 ms 58024 KiB
01-039.txt AC 499 ms 61612 KiB
01-040.txt AC 492 ms 61612 KiB
01-041.txt AC 336 ms 57252 KiB
01-042.txt AC 474 ms 61100 KiB
01-043.txt AC 266 ms 55724 KiB
01-044.txt AC 470 ms 60332 KiB
01-045.txt AC 289 ms 55980 KiB
01-046.txt AC 490 ms 59308 KiB
01-047.txt AC 263 ms 48552 KiB
01-048.txt AC 617 ms 51992 KiB
01-049.txt AC 836 ms 58396 KiB
01-050.txt AC 739 ms 58652 KiB