oj.uz

Submission #932720

# Submission time Handle Problem Language Result Execution time Memory
932720 2024-02-24T04:40:49 Z bachhoangxuan Mouse (info1cup19_mouse) C++17
100 / 100
 38 ms 952 KB 
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pii pair<int,int>
#define fi first
#define se second

void solve(int n) {
    rng.seed(998244353);
    vector<int> p(n);
    iota(p.begin(),p.end(),1);
    if(n==1){
        query(p);
        return;
    }
    while(true){
        int cnt=query(p);
        if(cnt==n) return;
        if(!cnt) break;
        shuffle(p.begin(),p.end(),rng);
    }

    //for(int x:p) cout << x << ' ';
    //cout << '\n';

    vector<int> c(n);
    iota(c.begin(),c.end(),0);
    int m=(n+1)/2;
    if(n&1) c.push_back(n);

    vector<int> res=p;
    vector<bool> used(n,false);
    vector<vector<int>> edge(n);

    for(int _=0;_<n;_++){
        vector<pii> s;
        for(int i=0;i<m;i++) if(c[i]<n && c[2*m-i-1]<n) s.push_back({c[i],c[2*m-i-1]});
        vector<int> pp=p;
        for(auto [x,y]:s) swap(pp[x],pp[y]);
        int cnt=query(pp);
        if(cnt==n) return;
        while(cnt){
            int l=0,r=(int)s.size()-2,val=0;
            while(l<=r){
                int mid=(l+r)>>1;pp=p;
                for(int i=0;i<=mid;i++) swap(pp[s[i].fi],pp[s[i].se]);
                int x=query(pp);
                if(x==n) return;
                if(x) val=x,r=mid-1;
                else l=mid+1;
            }
            if(!val) val=cnt;
            cnt-=val;
            auto [x,y]=s[l];
            if(val==2){
                swap(res[x],res[y]);
                used[x]=used[y]=false;
                //cout << "val " << x << ' ' << y << '\n';
            }
            else{
                //cout << "edge " << x << ' ' << y << '\n';
                edge[x].push_back(y);
                edge[y].push_back(x);
            }
            s.erase(s.begin(),s.begin()+l+1);
        }
        rotate(c.begin()+1,c.begin()+2,c.end());
    }
    for(int i=0;i<n;i++){
        if(used[i]) continue;
        int u=i;
        vector<int> v;
        do{
            used[u]=true;
            v.push_back(u);
            for(int x:edge[u]) if(!used[x]){u=x;break;}
            if(u==v.back()) break;
        }while(u!=i);
        int sz=(int)v.size();
        vector<int> pp=p;
        for(int i=0;i<sz-1;i++) swap(pp[v[i]],pp[v[i+1]]);
        int x=query(pp);
        if(x==n) return;
        if(x){
            for(int i=0;i<sz-1;i++) swap(res[v[i]],res[v[i+1]]);
        }
        else{
            for(int i=sz-2;i>=0;i--) swap(res[v[i]],res[v[i+1]]);
        }
    }
    int x=query(res);
    assert(x==n);
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 17
2 Correct 0 ms 344 KB Correct! Number of queries: 10
3 Correct 1 ms 344 KB Correct! Number of queries: 15
4 Correct 0 ms 344 KB Correct! Number of queries: 16
5 Correct 0 ms 344 KB Correct! Number of queries: 22
6 Correct 0 ms 344 KB Correct! Number of queries: 18

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 17
2 Correct 0 ms 344 KB Correct! Number of queries: 10
3 Correct 1 ms 344 KB Correct! Number of queries: 15
4 Correct 0 ms 344 KB Correct! Number of queries: 16
5 Correct 0 ms 344 KB Correct! Number of queries: 22
6 Correct 0 ms 344 KB Correct! Number of queries: 18
7 Correct 3 ms 600 KB Correct! Number of queries: 300
8 Correct 2 ms 436 KB Correct! Number of queries: 300
9 Correct 2 ms 432 KB Correct! Number of queries: 300
10 Correct 2 ms 436 KB Correct! Number of queries: 300
11 Correct 2 ms 440 KB Correct! Number of queries: 300
12 Correct 2 ms 440 KB Correct! Number of queries: 300
13 Correct 2 ms 436 KB Correct! Number of queries: 300
14 Correct 2 ms 440 KB Correct! Number of queries: 300
15 Correct 2 ms 440 KB Correct! Number of queries: 300
16 Correct 2 ms 436 KB Correct! Number of queries: 300

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 17
2 Correct 0 ms 344 KB Correct! Number of queries: 10
3 Correct 1 ms 344 KB Correct! Number of queries: 15
4 Correct 0 ms 344 KB Correct! Number of queries: 16
5 Correct 0 ms 344 KB Correct! Number of queries: 22
6 Correct 0 ms 344 KB Correct! Number of queries: 18
7 Correct 3 ms 600 KB Correct! Number of queries: 300
8 Correct 2 ms 436 KB Correct! Number of queries: 300
9 Correct 2 ms 432 KB Correct! Number of queries: 300
10 Correct 2 ms 436 KB Correct! Number of queries: 300
11 Correct 2 ms 440 KB Correct! Number of queries: 300
12 Correct 2 ms 440 KB Correct! Number of queries: 300
13 Correct 2 ms 436 KB Correct! Number of queries: 300
14 Correct 2 ms 440 KB Correct! Number of queries: 300
15 Correct 2 ms 440 KB Correct! Number of queries: 300
16 Correct 2 ms 436 KB Correct! Number of queries: 300
17 Correct 34 ms 696 KB Correct! Number of queries: 2000
18 Correct 33 ms 692 KB Correct! Number of queries: 1900
19 Correct 34 ms 684 KB Correct! Number of queries: 1900
20 Correct 36 ms 700 KB Correct! Number of queries: 2000
21 Correct 38 ms 444 KB Correct! Number of queries: 2000
22 Correct 31 ms 952 KB Correct! Number of queries: 1900
23 Correct 35 ms 696 KB Correct! Number of queries: 2000
24 Correct 38 ms 444 KB Correct! Number of queries: 2100
25 Correct 36 ms 692 KB Correct! Number of queries: 2000
26 Correct 38 ms 684 KB Correct! Number of queries: 2000