Submission #75821265

Source Code Expand

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

ll n,m;
ll a[1000010], t[1000010], z[2][1000010];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for (ll i=1;i<=n;i++) cin>>a[i];
    for (ll i=1;i<=m;i++) cin>>t[i];
    for (ll st=1;st<=1;st++)
    {
        ll l=st, r=st;
        for (ll i=st+1;i<=m;i++)
        {
            if (i>r)
            {
                l=i; r=i;
                while (r<=m&&t[r-l+st]==t[r]) r++;
                z[st][i]=r-l; r--;
            }
            else
            {
                ll k=i-l+st;
                if (z[st][k]<r-i+1) z[st][i]=z[st][k];
                else
                {
                    l=i;
                    while (r<=m&&t[r-l+st]==t[r]) r++;
                    z[st][i]=r-l; r--;
                }
            }
        }
    }
    z[1][1]=m;
    ll ans=m;
    for (ll i=2;i<=m;i++)
    {
        if (z[1][i]==m-i+1)
        {
            ans=i-1; break;
        }
    }
    multiset<ll> s;
    for (ll i=1;i<=n;i++) s.insert(a[i]);
    ll pos = 1;
    while (!s.empty())
    {
        auto idx = s.find(t[pos]);
        if (idx==s.end()) break;
        cout<<*idx<<" ";
        s.erase(idx);
        pos=(pos)%ans+1;
    }
    while (!s.empty())
    {
        cout<<(*s.begin())<<" ";
        s.erase(s.begin());
    }
}

Submission Info

Submission Time
Task C - Rearrangement
User prologue1017
Language C++23 (GCC 15.2.0)
Score 100
Code Size 1412 Byte
Status AC
Exec Time 1542 ms
Memory 77996 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 1 ms 3524 KiB
00-sample-002.txt AC 1 ms 3464 KiB
01-003.txt AC 1 ms 3652 KiB
01-004.txt AC 1 ms 3464 KiB
01-005.txt AC 1 ms 3556 KiB
01-006.txt AC 1 ms 3524 KiB
01-007.txt AC 1 ms 3516 KiB
01-008.txt AC 1 ms 3572 KiB
01-009.txt AC 309 ms 59824 KiB
01-010.txt AC 4 ms 4164 KiB
01-011.txt AC 31 ms 10300 KiB
01-012.txt AC 60 ms 15044 KiB
01-013.txt AC 100 ms 21336 KiB
01-014.txt AC 502 ms 61096 KiB
01-015.txt AC 333 ms 66216 KiB
01-016.txt AC 1457 ms 76716 KiB
01-017.txt AC 407 ms 60328 KiB
01-018.txt AC 1254 ms 67752 KiB
01-019.txt AC 262 ms 58292 KiB
01-020.txt AC 357 ms 61748 KiB
01-021.txt AC 316 ms 59048 KiB
01-022.txt AC 219 ms 60868 KiB
01-023.txt AC 243 ms 58204 KiB
01-024.txt AC 1287 ms 68012 KiB
01-025.txt AC 208 ms 58236 KiB
01-026.txt AC 326 ms 68292 KiB
01-027.txt AC 278 ms 58264 KiB
01-028.txt AC 302 ms 67544 KiB
01-029.txt AC 299 ms 58228 KiB
01-030.txt AC 248 ms 58292 KiB
01-031.txt AC 1542 ms 77736 KiB
01-032.txt AC 337 ms 59560 KiB
01-033.txt AC 1078 ms 64424 KiB
01-034.txt AC 741 ms 77988 KiB
01-035.txt AC 761 ms 77996 KiB
01-036.txt AC 738 ms 77996 KiB
01-037.txt AC 377 ms 71588 KiB
01-038.txt AC 359 ms 69292 KiB
01-039.txt AC 395 ms 76716 KiB
01-040.txt AC 379 ms 76712 KiB
01-041.txt AC 328 ms 68012 KiB
01-042.txt AC 380 ms 75436 KiB
01-043.txt AC 261 ms 64684 KiB
01-044.txt AC 371 ms 73896 KiB
01-045.txt AC 271 ms 65192 KiB
01-046.txt AC 380 ms 71852 KiB
01-047.txt AC 227 ms 55472 KiB
01-048.txt AC 632 ms 55468 KiB
01-049.txt AC 817 ms 62116 KiB
01-050.txt AC 714 ms 62376 KiB