Submission #75815033

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("O3,fast-math")
using namespace std;
using ll = long long;
int n,m,t,acnt[1010101],ans[1010101];
vector<int> b;
vector<int> ff(vector<int> a) {
  int sz=(int)a.size();
  vector<int> ret; ret.resize(sz);
  for(int i=1,j=0;i<sz;i++) {
    while(j && a[i]!=a[j]) j=ret[j-1];
    if(a[i]==a[j]) ret[i] = ++j;
  }
  return ret;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    b.resize(m+1);
    for(int i=1;i<=n;i++) {
        cin >> t;
        acnt[t]++;
    }
    for(int i=0;i<m;i++) cin >> b[i];

    // cut b
    auto F=ff(b);
    //cout << F[m-1] << endl;
    if(F[m-1]) m=m-F[m-1];
    
    int ptr=1; bool flag=true;
    while(flag) {
        for(int i=0;i<m;i++) {
            if(acnt[b[i]]) acnt[b[i]]--, ans[ptr++]=b[i];
            else {
                flag=false;
                break;
            }
        }
    }
    for(int i=1;i<=1000000;i++) {
        while(acnt[i]) ans[ptr++]=i, acnt[i]--;
    }
    for(int i=1;i<=n;i++) cout << ans[i] << " ";
}

Submission Info

Submission Time
Task C - Rearrangement
User Hakuaa_2
Language C++23 (GCC 15.2.0)
Score 100
Code Size 1098 Byte
Status AC
Exec Time 160 ms
Memory 23144 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 3 ms 3508 KiB
00-sample-002.txt AC 3 ms 3504 KiB
01-003.txt AC 3 ms 3592 KiB
01-004.txt AC 3 ms 3476 KiB
01-005.txt AC 3 ms 3516 KiB
01-006.txt AC 3 ms 3384 KiB
01-007.txt AC 3 ms 3528 KiB
01-008.txt AC 3 ms 3576 KiB
01-009.txt AC 74 ms 10920 KiB
01-010.txt AC 5 ms 3568 KiB
01-011.txt AC 13 ms 3928 KiB
01-012.txt AC 19 ms 4400 KiB
01-013.txt AC 28 ms 4704 KiB
01-014.txt AC 81 ms 13924 KiB
01-015.txt AC 85 ms 15824 KiB
01-016.txt AC 137 ms 22424 KiB
01-017.txt AC 83 ms 13224 KiB
01-018.txt AC 122 ms 17968 KiB
01-019.txt AC 63 ms 11512 KiB
01-020.txt AC 87 ms 13388 KiB
01-021.txt AC 76 ms 12032 KiB
01-022.txt AC 70 ms 12488 KiB
01-023.txt AC 63 ms 11452 KiB
01-024.txt AC 126 ms 18200 KiB
01-025.txt AC 75 ms 11460 KiB
01-026.txt AC 89 ms 16108 KiB
01-027.txt AC 74 ms 11380 KiB
01-028.txt AC 80 ms 15624 KiB
01-029.txt AC 72 ms 11440 KiB
01-030.txt AC 69 ms 11320 KiB
01-031.txt AC 121 ms 22924 KiB
01-032.txt AC 81 ms 12456 KiB
01-033.txt AC 98 ms 16284 KiB
01-034.txt AC 151 ms 23140 KiB
01-035.txt AC 160 ms 23140 KiB
01-036.txt AC 151 ms 23144 KiB
01-037.txt AC 103 ms 16020 KiB
01-038.txt AC 97 ms 17356 KiB
01-039.txt AC 114 ms 18584 KiB
01-040.txt AC 114 ms 18824 KiB
01-041.txt AC 96 ms 17964 KiB
01-042.txt AC 113 ms 17920 KiB
01-043.txt AC 87 ms 16460 KiB
01-044.txt AC 110 ms 17248 KiB
01-045.txt AC 91 ms 16640 KiB
01-046.txt AC 102 ms 16204 KiB
01-047.txt AC 70 ms 10400 KiB
01-048.txt AC 73 ms 13996 KiB
01-049.txt AC 83 ms 15272 KiB
01-050.txt AC 79 ms 15272 KiB