oj.uz

Submission #393894

# Submission time Handle Problem Language Result Execution time Memory
393894 2021-04-24T19:11:01 Z igzi Mouse (info1cup19_mouse) C++17
95.3846 / 100
 138 ms 944 KB 
#include <bits/stdc++.h>
#include "grader.h"
 
int query(vector<int> v);
 
typedef pair<int,int> pii;
 
#define fi first
#define se second
#define mp make_pair
 
vector<int> diff, cur;
 
const int N = 400;
vector<pii> lay[N];
int F[N][N];
bool vis[N];
 
vector<pii> cac;
 
int bins(int l, int r){
    vector<int> perm = diff;
    for(int j = l ; j <= r; j ++ ){
        swap(perm[cac[j].fi],perm[cac[j].se]);
    }
    int sol = query(perm);
    if(sol == 0){
        return 0;
    }
    if(l == r){
        F[cac[l].fi][cac[l].se] = F[cac[l].se][cac[l].fi] = sol;
        return sol;
    }
    else{
        int mid = (l + r) / 2;
        int xa = bins(l, mid);
        sol -= xa;
        if(sol > 0)
            bins(mid + 1, r);
    }
    return sol;
}
 
void solve(int n){
    for(int i = 0 ; i < n; i ++ ){
        cur.push_back(i + 1);
    }
    int sol;
    while(1){
        random_shuffle(cur.begin(), cur.end());
        sol = query(cur);
        if(sol == 0){
            diff = cur;
            break;
        }
        else if(sol == n){
            return;
        }
    }
    vector<pii> cur;
    cur.push_back(mp(0, n-1));
    vector<pii> nw;
    int mid;
    int id;
    int sz;
    int m;
    int nx;
    int li;
    while(!cur.empty()){
        nw.clear();
        for(int i = 0 ; i < N ; i ++ ){
            lay[i].clear();
        }
        for(auto x : cur){
            mid = (x.fi + x.se - 1) / 2;
            id = 0;
            sz = x.se - mid;
            for(int i = mid + 1; i <= x.se; i ++ ){
                for(int j = x.fi; j <= mid; j ++ ){
                    lay[id].push_back(mp(j, (mid+1) + ((j-x.fi+id)%sz)));
                }
                id ++ ;
            }
            if(x.fi != mid){
                nw.push_back(mp(x.fi, mid));
            }
            if(mid + 1 != x.se){
                nw.push_back(mp(mid + 1, x.se));
            }
        }
        int go;
        for(int i = 0 ; i < N ; i ++) {
            if(lay[i].empty()) continue;
            cac = lay[i];
            bins(0, (int)cac.size() - 1);
        }
        cur = nw;
    }
    int go = -1;
    vector<int> soln = diff;
    for(int i = 0 ; i < n; i ++ ){
        if(vis[i]) continue;
        go = -1;
        for(int j = 0 ; j < n; j ++ ){
            if(F[i][j] == 2){
                go = j;
            }
        }
        if(go != -1){
            vis[i]=true;
            vis[go]=true;
            swap(soln[i], soln[go]);
        }
        else{
            go = i;
            vector<int> cyc;
            bool mov = false;
            while(1){
                vis[go]=true;
                cyc.push_back(go);
                mov = false;
                for(int j = 0 ; j < n; j ++ ){
                    if(F[go][j] == 1 && !vis[j]){
                        go = j;
                        mov = true;
                        break;
                    }
                }
                if(!mov) break;
            }
            if(cyc.size() > 1){
                vector<int> perm = diff;
                for(int j = 0; j < cyc.size(); j ++ ){
                    perm[cyc[j]] = diff[cyc[(j - 1 + (int)cyc.size()) % (int)cyc.size()]];
                }
                sol = query(perm);
                if(sol == n) return;
                if(sol > 0){
                    for(int j = 0 ; j < cyc.size(); j ++ ){
                        soln[cyc[j]] = diff[cyc[(j - 1 + (int)cyc.size()) % (int)cyc.size()]];
                    }
                }
                else{
                    for(int j = 0 ; j < cyc.size(); j ++ ){
                        soln[cyc[j]] = diff[cyc[(j + 1) % cyc.size()]];
                    }
                }
            }
        }
    }
    query(soln);
}

Compilation message

mouse.cpp: In function 'void solve(int)':
mouse.cpp:91:13: warning: unused variable 'go' [-Wunused-variable]
   91 |         int go;
      |             ^~
mouse.cpp:133:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |                 for(int j = 0; j < cyc.size(); j ++ ){
      |                                ~~^~~~~~~~~~~~
mouse.cpp:139:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |                     for(int j = 0 ; j < cyc.size(); j ++ ){
      |                                     ~~^~~~~~~~~~~~
mouse.cpp:144:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |                     for(int j = 0 ; j < cyc.size(); j ++ ){
      |                                     ~~^~~~~~~~~~~~
mouse.cpp:66:9: warning: unused variable 'm' [-Wunused-variable]
   66 |     int m;
      |         ^
mouse.cpp:67:9: warning: unused variable 'nx' [-Wunused-variable]
   67 |     int nx;
      |         ^~
mouse.cpp:68:9: warning: unused variable 'li' [-Wunused-variable]
   68 |     int li;
      |         ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 24
2 Correct 1 ms 200 KB Correct! Number of queries: 5
3 Correct 1 ms 200 KB Correct! Number of queries: 17
4 Correct 1 ms 200 KB Correct! Number of queries: 25
5 Correct 1 ms 312 KB Correct! Number of queries: 27
6 Correct 1 ms 200 KB Correct! Number of queries: 29

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 24
2 Correct 1 ms 200 KB Correct! Number of queries: 5
3 Correct 1 ms 200 KB Correct! Number of queries: 17
4 Correct 1 ms 200 KB Correct! Number of queries: 25
5 Correct 1 ms 312 KB Correct! Number of queries: 27
6 Correct 1 ms 200 KB Correct! Number of queries: 29
7 Correct 7 ms 328 KB Correct! Number of queries: 400
8 Correct 8 ms 328 KB Correct! Number of queries: 400
9 Correct 6 ms 360 KB Correct! Number of queries: 400
10 Correct 7 ms 392 KB Correct! Number of queries: 400
11 Correct 6 ms 328 KB Correct! Number of queries: 400
12 Correct 6 ms 328 KB Correct! Number of queries: 400
13 Correct 8 ms 332 KB Correct! Number of queries: 400
14 Correct 8 ms 328 KB Correct! Number of queries: 400
15 Correct 6 ms 328 KB Correct! Number of queries: 400
16 Correct 7 ms 328 KB Correct! Number of queries: 400

Subtask #3
44.384592 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 24
2 Correct 1 ms 200 KB Correct! Number of queries: 5
3 Correct 1 ms 200 KB Correct! Number of queries: 17
4 Correct 1 ms 200 KB Correct! Number of queries: 25
5 Correct 1 ms 312 KB Correct! Number of queries: 27
6 Correct 1 ms 200 KB Correct! Number of queries: 29
7 Correct 7 ms 328 KB Correct! Number of queries: 400
8 Correct 8 ms 328 KB Correct! Number of queries: 400
9 Correct 6 ms 360 KB Correct! Number of queries: 400
10 Correct 7 ms 392 KB Correct! Number of queries: 400
11 Correct 6 ms 328 KB Correct! Number of queries: 400
12 Correct 6 ms 328 KB Correct! Number of queries: 400
13 Correct 8 ms 332 KB Correct! Number of queries: 400
14 Correct 8 ms 328 KB Correct! Number of queries: 400
15 Correct 6 ms 328 KB Correct! Number of queries: 400
16 Correct 7 ms 328 KB Correct! Number of queries: 400
17 Correct 124 ms 840 KB Correct! Number of queries: 2900
18 Correct 110 ms 840 KB Correct! Number of queries: 2800
19 Correct 112 ms 812 KB Correct! Number of queries: 2800
20 Correct 130 ms 940 KB Correct! Number of queries: 3000
21 Correct 119 ms 820 KB Correct! Number of queries: 2900
22 Correct 117 ms 924 KB Correct! Number of queries: 2800
23 Correct 118 ms 880 KB Correct! Number of queries: 2800
24 Correct 127 ms 744 KB Correct! Number of queries: 3000
25 Correct 138 ms 944 KB Correct! Number of queries: 3000
26 Correct 129 ms 896 KB Correct! Number of queries: 3000