oj.uz

Submission #717854

# Submission time Handle Problem Language Result Execution time Memory
717854 2023-04-02T16:16:58 Z Rafi22 The Collection Game (BOI21_swaps) C++14
0 / 100
 1 ms 208 KB 
#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)
{
    vector<vector<pair<int,int>>>res;
    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=60;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]);
            }
        }
    }
    answer(ans);
}

/*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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -