Submission #930694

#	Time	Username	Problem	Language	Result	Execution time	Memory
930694		socpite	Mouse (info1cup19_mouse)	C++14	51 / 100	3064 ms	720 KiB

mouse

#include<bits/stdc++.h>
#include"grader.h"
using namespace std;

const int maxn = 55;
int MAGIC = 7;

mt19937 rng(69420);

int n = 50;

vector<int> crr;

int cnt[maxn][maxn];
int pp[maxn][maxn];

vector<vector<int>> amon;
vector<int> perm;

void backtrack(int pos) {
    if(pos == n+1){
        amon.push_back(crr);
        return;
    }
    for(int i = 0; i < n; i++){
        if(crr[i]){
            continue;
        }
        bool chk = 1;
        for(int j = 0; j < MAGIC; j++){
            int tmp = i - pp[j][pos];
            tmp*=-1;
            if(tmp < 0)tmp += n;
            if(!cnt[j][tmp]){
                
                chk = 0;
                break;
            } 
        }
        if(!chk)continue;
        for(int j = 0; j < MAGIC; j++){
            int tmp = i - pp[j][pos];
            tmp*=-1;
            if(tmp < 0)tmp += n;
            cnt[j][tmp]--;
        }
        crr[i] = pos;
        backtrack(pos+1);
        crr[i] = 0;
        for(int j = 0; j < MAGIC; j++){
            int tmp = i - pp[j][pos];
            tmp*=-1;
            if(tmp < 0)tmp += n;
            cnt[j][tmp]++;
        }
    }
}


void solve (int N){
    n = N;
    ios::sync_with_stdio(false);
    cin.tie(0);
    crr.assign(n, 0);
    for(int i = 1; i <= n; i++)perm.push_back(i);
    shuffle(perm.begin(), perm.end(), rng);
    vector<int> rd = perm;
    for(int i = 0; i < MAGIC; i++){
        shuffle(rd.begin(), rd.end(), rng);
        for(int j = 0; j < n; j++)pp[i][rd[j]] = j;
        for(int j = 0; j < n; j++){
            cnt[i][j] = query(rd);
            if(cnt[i][j] == n)return;
            rd.push_back(rd[0]);
            rd.erase(rd.begin());
        }
    }
    backtrack(1);
    query(amon[0]);
}

• Subtask 1: 13 / 13
• Subtask 2: 38 / 38
• Subtask 3: 0 / 49