oj.uz

Submission #476925

# Submission time Handle Problem Language Result Execution time Memory
476925 2021-09-29T07:33:45 Z leaked Mouse (info1cup19_mouse) C++14
33.2184 / 100
 191 ms 200 KB 
#include <bits/stdc++.h>
#include "grader.h"
//#include "grader.cpp"

#define f first
#define s second
#define pb push_back
#define vec vector
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
typedef pair<int,int> pii;
typedef long double ld;
auto rng=bind(uniform_int_distribution<int>(1,1e9),mt19937(time(0)));
typedef long long ll;
const ll inf=1e18+100;
//const int N=49;
int query(vector<int> q);
int mx=0;
int tests=1000;
void solve(int n){
    /// let's try
    tests--;
    vec<int>pr(n);iota(all(pr),1);
    int cnt=(n>50?2398:n>7?398:49);cnt--;
//    vec<vec<ll>>answ(n,vec<ll>(n+1,0));
//    vec<vec<int>>cntt(n,vec<int>(n+1,0));
//    vec<int>how(n,n);
//    vec<int>p(n)
     map<vec<int>,int>gp;
    while(1){
        int how=query(pr);
        if(how==n) return;
        cnt--;
        if(how==0) break;
        random_shuffle(all(pr));
    }
    vec<vec<bool>>used(n,vec<bool>(n,0));
    if(n<=256){
        vec<bool>placed(n+1,0);
//        vec<vec<bool>>used(n,vec<bool>(n,0));
        int pv=0;
        for(int i=0;i<n;i++){
            for(int j=1;j<=n;j++){
                if(used[i][j]) continue;
                int t=-1;
                for(int k=0;k<n;k++){
                    if(pr[k]==j) t=k;
                }
                if(i==t) continue;
                used[i][j]=1;
                used[t][pr[i]]=1;
                swap(pr[i],pr[t]);
                int x=query(pr);
                if(x==n) return;
                if(x>pv){
                    pv=x;
                    continue;
                }
                swap(pr[i],pr[t]);
            }
        }
        assert(pv==n);
        return;
    }
    vec<int>bad;
    for(int i=1;i<=n;i++) bad.pb(i);
    int x=0;
    while(x!=n){
//        cout<<"ASK"<<endl;
        int i=rng()%n,j=rng()%sz(bad);
        for(int t=0;t<n;t++){

        }
        swap(pr[i],pr[j]);
        int y=query(pr);
        if(y==n) break;
        if(y>x) continue;
        else swap(pr[i],pr[j]);
    }
    query(pr);
    return ;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 12
2 Correct 1 ms 200 KB Correct! Number of queries: 7
3 Correct 1 ms 200 KB Correct! Number of queries: 21
4 Correct 1 ms 200 KB Correct! Number of queries: 23
5 Correct 1 ms 200 KB Correct! Number of queries: 15
6 Correct 1 ms 200 KB Correct! Number of queries: 28

Subtask #2
20.218394 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 12
2 Correct 1 ms 200 KB Correct! Number of queries: 7
3 Correct 1 ms 200 KB Correct! Number of queries: 21
4 Correct 1 ms 200 KB Correct! Number of queries: 23
5 Correct 1 ms 200 KB Correct! Number of queries: 15
6 Correct 1 ms 200 KB Correct! Number of queries: 28
7 Correct 27 ms 200 KB Correct! Number of queries: 1600
8 Correct 27 ms 200 KB Correct! Number of queries: 1600
9 Correct 22 ms 200 KB Correct! Number of queries: 1300
10 Correct 21 ms 200 KB Correct! Number of queries: 1600
11 Correct 16 ms 200 KB Correct! Number of queries: 1100
12 Correct 25 ms 200 KB Correct! Number of queries: 1500
13 Correct 24 ms 200 KB Correct! Number of queries: 1400
14 Correct 17 ms 200 KB Correct! Number of queries: 1300
15 Correct 28 ms 200 KB Correct! Number of queries: 1700
16 Correct 26 ms 200 KB Correct! Number of queries: 1600

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 12
2 Correct 1 ms 200 KB Correct! Number of queries: 7
3 Correct 1 ms 200 KB Correct! Number of queries: 21
4 Correct 1 ms 200 KB Correct! Number of queries: 23
5 Correct 1 ms 200 KB Correct! Number of queries: 15
6 Correct 1 ms 200 KB Correct! Number of queries: 28
7 Correct 27 ms 200 KB Correct! Number of queries: 1600
8 Correct 27 ms 200 KB Correct! Number of queries: 1600
9 Correct 22 ms 200 KB Correct! Number of queries: 1300
10 Correct 21 ms 200 KB Correct! Number of queries: 1600
11 Correct 16 ms 200 KB Correct! Number of queries: 1100
12 Correct 25 ms 200 KB Correct! Number of queries: 1500
13 Correct 24 ms 200 KB Correct! Number of queries: 1400
14 Correct 17 ms 200 KB Correct! Number of queries: 1300
15 Correct 28 ms 200 KB Correct! Number of queries: 1700
16 Correct 26 ms 200 KB Correct! Number of queries: 1600
17 Runtime error 191 ms 200 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -