Submission #717857

#	Time	Username	Problem	Language	Result	Execution time	Memory
717857		Rafi22	The Collection Game (BOI21_swaps)	C++14	100 / 100	7 ms	580 KiB

swaps

#include <bits/stdc++.h>
#include "swaps.h"

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=507;
/*
int p[N];
vector<pair<int,int>>tmp;

void schedule(int a,int b)
{
    tmp.pb({a,b});
}

vector<int>visit()
{
    vector<int>res;
    for(auto x:tmp) res.pb(p[x.st]>p[x.nd]);
    tmp.clear();
    return res;
}


void answer(vector<int>V)
{
    for(auto x:V) cout<<x<<" ";
    cout<<endl;
}
*/
vector<pair<pair<int,int>,int>>V[100];

void rek1(int l,int r,bool is,int D)
{
    if(l==r) return ;
    for(int i=l;i<=(l+r)/2;i++)
    {
        V[D].pb({{i,i+(r-l+1)/2},is});
    }
    rek1(l,(l+r)/2,is,D-1);
    rek1((l+r)/2+1,r,is,D-1);
}

void rek(int l,int r,bool is,int D,int c)
{
    if(l==r) return ;
    rek1(l,r,is,D+c);
    rek(l,(l+r)/2,0,D+c,c-1);
    rek((l+r)/2+1,r,1,D+c,c-1);
}

void solve(int n,int v)
{
    int p=1,c=0;
    while(p<n)
    {
        c++;
        p*=2;
    }
    rek(1,p,0,0,c);
    vector<int>ans(p);
    for(int i=0;i<p;i++) ans[i]=i+1;
    for(int i=50;i>0;i--)
    {
        for(auto x:V[i])
        {
            if(max(ans[x.st.st-1],ans[x.st.nd-1])>n) continue;
            schedule(ans[x.st.st-1],ans[x.st.nd-1]);
        }
        vector<int>A=visit();
        int it=0;
        for(auto x:V[i])
        {
            if(max(ans[x.st.st-1],ans[x.st.nd-1])<=n)
            {
                if(A[it]==x.nd) swap(ans[x.st.st-1],ans[x.st.nd-1]);
                it++;
            }
            else
            {
                if(ans[x.st.nd-1]>n&&x.nd) swap(ans[x.st.st-1],ans[x.st.nd-1]);
                if(ans[x.st.st-1]>n&&!x.nd) swap(ans[x.st.st-1],ans[x.st.nd-1]);
            }
        }
    }
    vector<int>res(n);
    for(int i=0;i<n;i++) res[i]=ans[i];
    answer(res);
 }

/*int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i];
    solve(n,0);
    return 0;
}

10
5 2 10 6 1 8 9 4 7 3
*/

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 9 / 9
• Subtask 6: 6 / 6
• Subtask 7: 9 / 9
• Subtask 8: 6 / 6
• Subtask 9: 21 / 21
• Subtask 10: 14 / 14
• Subtask 11: 9 / 9
• Subtask 12: 6 / 6