oj.uz

Submission #930738

# Submission time Handle Problem Language Result Execution time Memory
930738 2024-02-20T10:58:56 Z socpite Mouse (info1cup19_mouse) C++14
92.3077 / 100
 125 ms 2036 KB 
#include<bits/stdc++.h>
#include"grader.h"
using namespace std;

const int maxn = 260;
int MAGIC = 12;

mt19937 rng(69420);

int n = 260;

vector<int> crr;

int cnt[maxn][maxn];
int pp[maxn][maxn];
int dead[maxn][maxn];
vector<int> possible[maxn];

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

void backtrack(int pos) {
    if(pos == n+1){
        amon.push_back(crr);
        return;
    }
    for(int i: possible[pos]){
        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]++;
        }
    }
}

// int query(vector<int> Q){
//     int cnt = 0;
//     for(int i = 0; i < n; i++){
//         if(Q[i] == perm[i])cnt++;
//     }
//     // cout << cnt << endl;
//     return cnt;
// }

void solve(int N){
    n = N;
    if(n <= 50)MAGIC = 7;
    else MAGIC = 13;
    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;
            if(cnt[i][j] == 0){
                for(int k = 0; k < n; k++)dead[rd[j]][j] = 1;
            }
            rd.push_back(rd[0]);
            rd.erase(rd.begin());
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < n; j++)if(!dead[i][j])possible[i].push_back(j);
        // cout << possible[i].size() << endl;
    }
    // return;
    backtrack(1);
    // cout << amon.size();
    query(amon[0]);
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Correct! Number of queries: 50
2 Correct 0 ms 464 KB Correct! Number of queries: 29
3 Correct 1 ms 452 KB Correct! Number of queries: 43
4 Correct 0 ms 464 KB Correct! Number of queries: 50
5 Correct 1 ms 464 KB Correct! Number of queries: 50
6 Correct 1 ms 460 KB Correct! Number of queries: 50

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Correct! Number of queries: 50
2 Correct 0 ms 464 KB Correct! Number of queries: 29
3 Correct 1 ms 452 KB Correct! Number of queries: 43
4 Correct 0 ms 464 KB Correct! Number of queries: 50
5 Correct 1 ms 464 KB Correct! Number of queries: 50
6 Correct 1 ms 460 KB Correct! Number of queries: 50
7 Correct 3 ms 1264 KB Correct! Number of queries: 400
8 Correct 4 ms 724 KB Correct! Number of queries: 400
9 Correct 2 ms 456 KB Correct! Number of queries: 400
10 Correct 4 ms 972 KB Correct! Number of queries: 400
11 Correct 2 ms 716 KB Correct! Number of queries: 300
12 Correct 3 ms 720 KB Correct! Number of queries: 400
13 Correct 3 ms 716 KB Correct! Number of queries: 400
14 Correct 3 ms 716 KB Correct! Number of queries: 400
15 Correct 3 ms 456 KB Correct! Number of queries: 400
16 Correct 9 ms 716 KB Correct! Number of queries: 400

Subtask #3
41.307686 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Correct! Number of queries: 50
2 Correct 0 ms 464 KB Correct! Number of queries: 29
3 Correct 1 ms 452 KB Correct! Number of queries: 43
4 Correct 0 ms 464 KB Correct! Number of queries: 50
5 Correct 1 ms 464 KB Correct! Number of queries: 50
6 Correct 1 ms 460 KB Correct! Number of queries: 50
7 Correct 3 ms 1264 KB Correct! Number of queries: 400
8 Correct 4 ms 724 KB Correct! Number of queries: 400
9 Correct 2 ms 456 KB Correct! Number of queries: 400
10 Correct 4 ms 972 KB Correct! Number of queries: 400
11 Correct 2 ms 716 KB Correct! Number of queries: 300
12 Correct 3 ms 720 KB Correct! Number of queries: 400
13 Correct 3 ms 716 KB Correct! Number of queries: 400
14 Correct 3 ms 716 KB Correct! Number of queries: 400
15 Correct 3 ms 456 KB Correct! Number of queries: 400
16 Correct 9 ms 716 KB Correct! Number of queries: 400
17 Correct 77 ms 1212 KB Correct! Number of queries: 3400
18 Correct 76 ms 1256 KB Correct! Number of queries: 3200
19 Correct 68 ms 1592 KB Correct! Number of queries: 3200
20 Correct 64 ms 1248 KB Correct! Number of queries: 3400
21 Correct 60 ms 2036 KB Correct! Number of queries: 3300
22 Correct 68 ms 1248 KB Correct! Number of queries: 3200
23 Correct 66 ms 1724 KB Correct! Number of queries: 3300
24 Correct 73 ms 1308 KB Correct! Number of queries: 3400
25 Correct 73 ms 1756 KB Correct! Number of queries: 3400
26 Correct 125 ms 1168 KB Correct! Number of queries: 3400