oj.uz

Submission #370233

# Submission time Handle Problem Language Result Execution time Memory
370233 2021-02-23T15:19:22 Z doowey Mouse (info1cup19_mouse) C++14
88.5385 / 100
 161 ms 1060 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;

void 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;
    }
    if(l == r){
        F[cac[l].fi][cac[l].se] = F[cac[l].se][cac[l].fi] = sol;
        return ;
    }
    else{
        int mid = (l + r) / 2;
        bins(l, mid);
        bins(mid + 1, r);
    }
}

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:88:13: warning: unused variable 'go' [-Wunused-variable]
   88 |         int go;
      |             ^~
mouse.cpp:130:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |                 for(int j = 0; j < cyc.size(); j ++ ){
      |                                ~~^~~~~~~~~~~~
mouse.cpp:136:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |                     for(int j = 0 ; j < cyc.size(); j ++ ){
      |                                     ~~^~~~~~~~~~~~
mouse.cpp:141:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |                     for(int j = 0 ; j < cyc.size(); j ++ ){
      |                                     ~~^~~~~~~~~~~~
mouse.cpp:63:9: warning: unused variable 'm' [-Wunused-variable]
   63 |     int m;
      |         ^
mouse.cpp:64:9: warning: unused variable 'nx' [-Wunused-variable]
   64 |     int nx;
      |         ^~
mouse.cpp:65:9: warning: unused variable 'li' [-Wunused-variable]
   65 |     int li;
      |         ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Correct! Number of queries: 27
2 Correct 1 ms 364 KB Correct! Number of queries: 5
3 Correct 1 ms 364 KB Correct! Number of queries: 19
4 Correct 1 ms 364 KB Correct! Number of queries: 29
5 Correct 1 ms 364 KB Correct! Number of queries: 30
6 Correct 1 ms 364 KB Correct! Number of queries: 30

Subtask #2
35.000014 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Correct! Number of queries: 27
2 Correct 1 ms 364 KB Correct! Number of queries: 5
3 Correct 1 ms 364 KB Correct! Number of queries: 19
4 Correct 1 ms 364 KB Correct! Number of queries: 29
5 Correct 1 ms 364 KB Correct! Number of queries: 30
6 Correct 1 ms 364 KB Correct! Number of queries: 30
7 Correct 8 ms 364 KB Correct! Number of queries: 500
8 Correct 8 ms 364 KB Correct! Number of queries: 500
9 Correct 8 ms 364 KB Correct! Number of queries: 500
10 Correct 9 ms 364 KB Correct! Number of queries: 500
11 Correct 6 ms 364 KB Correct! Number of queries: 400
12 Correct 9 ms 364 KB Correct! Number of queries: 500
13 Correct 8 ms 428 KB Correct! Number of queries: 500
14 Correct 9 ms 364 KB Correct! Number of queries: 500
15 Correct 8 ms 364 KB Correct! Number of queries: 500
16 Correct 9 ms 364 KB Correct! Number of queries: 500

Subtask #3
40.538484 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Correct! Number of queries: 27
2 Correct 1 ms 364 KB Correct! Number of queries: 5
3 Correct 1 ms 364 KB Correct! Number of queries: 19
4 Correct 1 ms 364 KB Correct! Number of queries: 29
5 Correct 1 ms 364 KB Correct! Number of queries: 30
6 Correct 1 ms 364 KB Correct! Number of queries: 30
7 Correct 8 ms 364 KB Correct! Number of queries: 500
8 Correct 8 ms 364 KB Correct! Number of queries: 500
9 Correct 8 ms 364 KB Correct! Number of queries: 500
10 Correct 9 ms 364 KB Correct! Number of queries: 500
11 Correct 6 ms 364 KB Correct! Number of queries: 400
12 Correct 9 ms 364 KB Correct! Number of queries: 500
13 Correct 8 ms 428 KB Correct! Number of queries: 500
14 Correct 9 ms 364 KB Correct! Number of queries: 500
15 Correct 8 ms 364 KB Correct! Number of queries: 500
16 Correct 9 ms 364 KB Correct! Number of queries: 500
17 Correct 152 ms 1060 KB Correct! Number of queries: 3400
18 Correct 156 ms 872 KB Correct! Number of queries: 3300
19 Correct 151 ms 852 KB Correct! Number of queries: 3300
20 Correct 161 ms 984 KB Correct! Number of queries: 3500
21 Correct 151 ms 876 KB Correct! Number of queries: 3400
22 Correct 142 ms 1004 KB Correct! Number of queries: 3300
23 Correct 141 ms 928 KB Correct! Number of queries: 3300
24 Correct 143 ms 1016 KB Correct! Number of queries: 3500
25 Correct 159 ms 936 KB Correct! Number of queries: 3500
26 Correct 158 ms 940 KB Correct! Number of queries: 3500