oj.uz

Submission #717857

# Submission time Handle Problem Language Result Execution time Memory
717857 2023-04-02T16:19:57 Z Rafi22 The Collection Game (BOI21_swaps) C++14
100 / 100
 7 ms 580 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)
{
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 336 KB Correct
4 Correct 5 ms 464 KB Correct
5 Correct 5 ms 460 KB Correct
6 Correct 5 ms 464 KB Correct
7 Correct 5 ms 460 KB Correct
8 Correct 6 ms 464 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 3 ms 336 KB Correct
4 Correct 6 ms 468 KB Correct
5 Correct 5 ms 460 KB Correct
6 Correct 4 ms 464 KB Correct
7 Correct 5 ms 464 KB Correct
8 Correct 5 ms 468 KB Correct
9 Correct 5 ms 464 KB Correct
10 Correct 6 ms 464 KB Correct
11 Correct 5 ms 456 KB Correct
12 Correct 6 ms 464 KB Correct
13 Correct 5 ms 516 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 1 ms 208 KB Correct
4 Correct 2 ms 208 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 376 KB Correct
4 Correct 5 ms 464 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 376 KB Correct
4 Correct 5 ms 464 KB Correct
5 Correct 1 ms 208 KB Correct
6 Correct 2 ms 256 KB Correct
7 Correct 2 ms 336 KB Correct
8 Correct 5 ms 468 KB Correct
9 Correct 5 ms 464 KB Correct
10 Correct 6 ms 460 KB Correct
11 Correct 5 ms 464 KB Correct
12 Correct 6 ms 580 KB Correct
13 Correct 1 ms 208 KB Correct
14 Correct 1 ms 208 KB Correct
15 Correct 2 ms 376 KB Correct
16 Correct 5 ms 460 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 336 KB Correct
4 Correct 5 ms 464 KB Correct
5 Correct 4 ms 468 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 336 KB Correct
4 Correct 5 ms 464 KB Correct
5 Correct 4 ms 468 KB Correct
6 Correct 1 ms 208 KB Correct
7 Correct 2 ms 208 KB Correct
8 Correct 3 ms 376 KB Correct
9 Correct 5 ms 468 KB Correct
10 Correct 6 ms 460 KB Correct
11 Correct 5 ms 464 KB Correct
12 Correct 6 ms 468 KB Correct
13 Correct 6 ms 460 KB Correct
14 Correct 5 ms 468 KB Correct
15 Correct 4 ms 460 KB Correct
16 Correct 4 ms 464 KB Correct
17 Correct 5 ms 464 KB Correct
18 Correct 5 ms 460 KB Correct
19 Correct 1 ms 208 KB Correct
20 Correct 1 ms 208 KB Correct
21 Correct 3 ms 336 KB Correct
22 Correct 5 ms 472 KB Correct
23 Correct 5 ms 460 KB Correct

Subtask #9
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 376 KB Correct
4 Correct 6 ms 464 KB Correct
5 Correct 5 ms 444 KB Correct
6 Correct 6 ms 444 KB Correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 376 KB Correct
4 Correct 6 ms 464 KB Correct
5 Correct 5 ms 444 KB Correct
6 Correct 6 ms 444 KB Correct
7 Correct 1 ms 208 KB Correct
8 Correct 1 ms 208 KB Correct
9 Correct 2 ms 336 KB Correct
10 Correct 5 ms 460 KB Correct
11 Correct 4 ms 460 KB Correct
12 Correct 4 ms 460 KB Correct
13 Correct 5 ms 464 KB Correct
14 Correct 4 ms 464 KB Correct
15 Correct 5 ms 460 KB Correct
16 Correct 4 ms 468 KB Correct
17 Correct 4 ms 460 KB Correct
18 Correct 4 ms 464 KB Correct
19 Correct 5 ms 460 KB Correct
20 Correct 1 ms 208 KB Correct
21 Correct 1 ms 208 KB Correct
22 Correct 2 ms 372 KB Correct
23 Correct 7 ms 460 KB Correct
24 Correct 5 ms 460 KB Correct
25 Correct 5 ms 440 KB Correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 2 ms 208 KB Correct
3 Correct 3 ms 336 KB Correct
4 Correct 5 ms 460 KB Correct
5 Correct 4 ms 452 KB Correct
6 Correct 5 ms 444 KB Correct
7 Correct 5 ms 444 KB Correct

Subtask #12
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 2 ms 208 KB Correct
3 Correct 3 ms 336 KB Correct
4 Correct 5 ms 460 KB Correct
5 Correct 4 ms 452 KB Correct
6 Correct 5 ms 444 KB Correct
7 Correct 5 ms 444 KB Correct
8 Correct 1 ms 208 KB Correct
9 Correct 1 ms 208 KB Correct
10 Correct 1 ms 208 KB Correct
11 Correct 3 ms 336 KB Correct
12 Correct 5 ms 464 KB Correct
13 Correct 5 ms 460 KB Correct
14 Correct 4 ms 464 KB Correct
15 Correct 5 ms 536 KB Correct
16 Correct 5 ms 464 KB Correct
17 Correct 6 ms 460 KB Correct
18 Correct 5 ms 464 KB Correct
19 Correct 5 ms 468 KB Correct
20 Correct 5 ms 464 KB Correct
21 Correct 5 ms 580 KB Correct
22 Correct 1 ms 280 KB Correct
23 Correct 1 ms 208 KB Correct
24 Correct 3 ms 336 KB Correct
25 Correct 6 ms 464 KB Correct
26 Correct 5 ms 464 KB Correct
27 Correct 6 ms 440 KB Correct
28 Correct 6 ms 440 KB Correct