Submission #75816405

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
const int MXN=1e6;

int N,M,A[MXN],B[MXN],pi[MXN],cnt[MXN+1];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin>>N>>M;
    for(int i=0;i<N;i++) cin>>A[i];
    for(int i=0;i<M;i++) cin>>B[i];
    
    for(int i=0;i<N;i++) cnt[A[i]]++;
    
    pi[0]=0;
    int j=0;
    for(int i=1;i<N;i++){
        while(j>0&&B[i]!=B[j]) j=pi[j-1];
        if(B[i]==B[j]) pi[i]=++j;
    }

    for(int i=0,j=0;i<N;i++) {
        while(j>0&&!cnt[B[j]]) j=pi[j-1];
        
        if(!cnt[B[j]]) break;

        cout<<B[j]<<' ';
        cnt[B[j]]--;j++;
        if(j==M) j=pi[j-1];
        continue;
    }

    for(int i=0;i<=MXN;i++) while(cnt[i]--) cout<<i<<' ';
}

Submission Info

Submission Time
Task C - Rearrangement
User strain7626
Language C++23 (GCC 15.2.0)
Score 100
Code Size 744 Byte
Status AC
Exec Time 101 ms
Memory 22952 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 5 ms 7412 KiB
00-sample-002.txt AC 3 ms 7404 KiB
01-003.txt AC 3 ms 7404 KiB
01-004.txt AC 3 ms 7364 KiB
01-005.txt AC 3 ms 7376 KiB
01-006.txt AC 3 ms 7404 KiB
01-007.txt AC 3 ms 7404 KiB
01-008.txt AC 3 ms 7492 KiB
01-009.txt AC 63 ms 15016 KiB
01-010.txt AC 5 ms 7484 KiB
01-011.txt AC 11 ms 7792 KiB
01-012.txt AC 15 ms 8184 KiB
01-013.txt AC 23 ms 8700 KiB
01-014.txt AC 63 ms 14076 KiB
01-015.txt AC 71 ms 15788 KiB
01-016.txt AC 101 ms 20396 KiB
01-017.txt AC 64 ms 13228 KiB
01-018.txt AC 83 ms 16812 KiB
01-019.txt AC 48 ms 11344 KiB
01-020.txt AC 70 ms 16812 KiB
01-021.txt AC 57 ms 11944 KiB
01-022.txt AC 55 ms 12528 KiB
01-023.txt AC 49 ms 11312 KiB
01-024.txt AC 83 ms 16808 KiB
01-025.txt AC 60 ms 15172 KiB
01-026.txt AC 71 ms 16368 KiB
01-027.txt AC 58 ms 11544 KiB
01-028.txt AC 64 ms 15916 KiB
01-029.txt AC 58 ms 11372 KiB
01-030.txt AC 53 ms 11344 KiB
01-031.txt AC 94 ms 22952 KiB
01-032.txt AC 65 ms 12456 KiB
01-033.txt AC 71 ms 16040 KiB
01-034.txt AC 100 ms 19112 KiB
01-035.txt AC 100 ms 19120 KiB
01-036.txt AC 100 ms 19120 KiB
01-037.txt AC 84 ms 20136 KiB
01-038.txt AC 78 ms 18860 KiB
01-039.txt AC 93 ms 22440 KiB
01-040.txt AC 94 ms 22704 KiB
01-041.txt AC 74 ms 18092 KiB
01-042.txt AC 91 ms 21932 KiB
01-043.txt AC 68 ms 16548 KiB
01-044.txt AC 88 ms 21164 KiB
01-045.txt AC 71 ms 16812 KiB
01-046.txt AC 84 ms 20140 KiB
01-047.txt AC 57 ms 14244 KiB
01-048.txt AC 56 ms 14252 KiB
01-049.txt AC 67 ms 15052 KiB
01-050.txt AC 63 ms 15272 KiB