Submission #476924

#	Time	Username	Problem	Language	Result	Execution time	Memory
476924		leaked	Mouse (info1cup19_mouse)	C++14	13 / 100	98 ms	200 KiB

mouse

#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));
    }
    if(n<=7){
        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;
    }
    int x=0;
    while(x!=n){
//        cout<<"ASK"<<endl;
        int i=rng()%n,j=rng()%n;
        while(i==j) j=rng()%n;
        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 / 13
• Subtask 2: 0 / 38
• Subtask 3: 0 / 49