oj.uz

Submission #755739

# Submission time Handle Problem Language Result Execution time Memory
755739 2023-06-10T15:36:26 Z DJeniUp Mouse (info1cup19_mouse) C++17
45 / 100
 186 ms 292 KB 
#include "bits/stdc++.h"
#include "grader.h"

int query(vector<int> v);

typedef long long ll;
 
#define pb push_back
 
vector<int>v,a[5],h,l;
 
ll f[307];
 
void solve(int n){
    for(int i=1;i<=n;i++){
        v.pb(i);
    }
    for(int i=0;i<n*n;i++){
        ll x=(rand()+clock())%n;
        ll y=(rand()+clock())%n;
        swap(v[x],v[y]);
    }
    
    ll x=query(v);
    if(x==n)return ;
    for(int i=1;i<n;i++){
        swap(v[0],v[i]);
        ll y=query(v);
        a[y-x+2].pb(i);
        swap(v[0],v[i]);
    }
    if(a[2].size()==0 && a[3].size()==0 && a[4].size()==0){
        f[0]=1;
        for(auto it:a[0]){
            f[it]=1;
        }
    }else{
        for(auto it:a[1]){
            f[it]=1;
        }
        if(a[4].size()==1){
            swap(v[0],v[a[4][0]]);
            f[0]=1;
            f[a[4][0]]=1;
            x+=2;
        }else{
            swap(v[0],v[a[3][0]]);
            swap(v[0],v[a[3][1]]);
            ll y=query(v);
            if(y==n)return ;
            if(y-x==2){
                f[0]=1;
                f[a[3][0]]=1;
                x=y;
            }else if(y-x==3){
                f[0]=1;
                f[a[3][0]]=1;
                f[a[3][1]]=1;
                x=y;
            }else{
                swap(v[0],v[a[3][1]]);
                swap(v[0],v[a[3][0]]);
                
                swap(v[0],v[a[3][1]]);
                swap(v[0],v[a[3][0]]);
                y=query(v);
                if(y==n)return ;
                if(y-x==2){
                    f[0]=1;
                    f[a[3][1]]=1;
                    x=y;
                }else if(y-x==3){
                    f[0]=1;
                    f[a[3][0]]=1;
                    f[a[3][1]]=1;
                    x=y;
                }
            }
        }
    }
    h.pb(0);
    while(h.size()>0){
        h.clear();
        
        for(int i=0;i<n;i++){
            if(f[i]==0){
                h.pb(i);
                //cout<<i<<" ";
            }
        }
        ll z1=rand()%3;
        while(z1==0)z1=rand()%3;
        while(z1--){
            for(int i=1;i<h.size();i++){
                swap(v[h[i-1]],v[h[i]]);
            }
            
            if(h.size()!=2)swap(v[h[0]],v[h[h.size()-1]]);
        }
        ll y=query(v);
        ll y1=y;
        if(y==n)return ;
        if(x!=y){
            for(auto i:h){
                swap(v[0],v[i]);
                ll z=query(v);
                if(z-y==-2){
                    f[i]=1;
                    y1--;
                }
                swap(v[0],v[i]);
                if(y1==x)break;
            }
        }
        x=y;
    }
    return ;
}

Compilation message

mouse.cpp: In function 'void solve(int)':
mouse.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for(int i=1;i<h.size();i++){
      |                         ~^~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct! Number of queries: 19
2 Correct 1 ms 208 KB Correct! Number of queries: 9
3 Correct 1 ms 208 KB Correct! Number of queries: 12
4 Correct 1 ms 208 KB Correct! Number of queries: 24
5 Correct 1 ms 208 KB Correct! Number of queries: 17
6 Correct 1 ms 208 KB Correct! Number of queries: 18

Subtask #2
31.99999 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct! Number of queries: 19
2 Correct 1 ms 208 KB Correct! Number of queries: 9
3 Correct 1 ms 208 KB Correct! Number of queries: 12
4 Correct 1 ms 208 KB Correct! Number of queries: 24
5 Correct 1 ms 208 KB Correct! Number of queries: 17
6 Correct 1 ms 208 KB Correct! Number of queries: 18
7 Correct 8 ms 208 KB Correct! Number of queries: 600
8 Correct 10 ms 208 KB Correct! Number of queries: 600
9 Correct 6 ms 208 KB Correct! Number of queries: 400
10 Correct 9 ms 208 KB Correct! Number of queries: 600
11 Correct 6 ms 208 KB Correct! Number of queries: 400
12 Correct 8 ms 292 KB Correct! Number of queries: 500
13 Correct 6 ms 208 KB Correct! Number of queries: 400
14 Correct 9 ms 208 KB Correct! Number of queries: 500
15 Correct 9 ms 208 KB Correct! Number of queries: 500
16 Correct 10 ms 208 KB Correct! Number of queries: 600

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct! Number of queries: 19
2 Correct 1 ms 208 KB Correct! Number of queries: 9
3 Correct 1 ms 208 KB Correct! Number of queries: 12
4 Correct 1 ms 208 KB Correct! Number of queries: 24
5 Correct 1 ms 208 KB Correct! Number of queries: 17
6 Correct 1 ms 208 KB Correct! Number of queries: 18
7 Correct 8 ms 208 KB Correct! Number of queries: 600
8 Correct 10 ms 208 KB Correct! Number of queries: 600
9 Correct 6 ms 208 KB Correct! Number of queries: 400
10 Correct 9 ms 208 KB Correct! Number of queries: 600
11 Correct 6 ms 208 KB Correct! Number of queries: 400
12 Correct 8 ms 292 KB Correct! Number of queries: 500
13 Correct 6 ms 208 KB Correct! Number of queries: 400
14 Correct 9 ms 208 KB Correct! Number of queries: 500
15 Correct 9 ms 208 KB Correct! Number of queries: 500
16 Correct 10 ms 208 KB Correct! Number of queries: 600
17 Runtime error 186 ms 292 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -