oj.uz

답안 #369869

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
369869 2021-02-22T16:36:02 Z doowey Mouse (info1cup19_mouse) C++14
99.2308 / 100
 120 ms 1116 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];

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;
            vector<int> perm = diff;
            for(auto x : lay[i])
                swap(perm[x.fi], perm[x.se]);
            sol = query(perm);
            if(sol == n) return;
            li = -1;
            go = sol;
            int en = 0;
            while(go > 0){
                en = li + 1;
                for(int lg = 9 ; lg >= 0 ;lg -- ){
                    nx = en + (1 << lg);
                    if(nx > lay[i].size()) continue;
                    perm = diff;
                    for(int t = li + 1 ; t < nx; t ++ )
                        swap(perm[lay[i][t].fi], perm[lay[i][t].se]);
                    sol = query(perm);
                    if(sol == n) return;
                    if(sol == 0)
                        en = nx;
                }
                li = en;
                perm = diff;
                swap(perm[lay[i][li].fi], perm[lay[i][li].se]);
                sol = query(perm);
                if(sol == n) return;
                go -= sol;
                F[lay[i][li].fi][lay[i][li].se] = F[lay[i][li].se][lay[i][li].fi] = sol;
            }
        }
        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:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                     if(nx > lay[i].size()) continue;
      |                        ~~~^~~~~~~~~~~~~~~
mouse.cpp:135:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |                 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:146:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |                     for(int j = 0 ; j < cyc.size(); j ++ ){
      |                                     ~~^~~~~~~~~~~~
mouse.cpp:41:9: warning: unused variable 'm' [-Wunused-variable]
   41 |     int m;
      |         ^

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 368 KB Correct! Number of queries: 32
2 Correct 1 ms 364 KB Correct! Number of queries: 5
3 Correct 1 ms 364 KB Correct! Number of queries: 23
4 Correct 1 ms 364 KB Correct! Number of queries: 28
5 Correct 1 ms 364 KB Correct! Number of queries: 32
6 Correct 2 ms 364 KB Correct! Number of queries: 35

Subtask #2
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 368 KB Correct! Number of queries: 32
2 Correct 1 ms 364 KB Correct! Number of queries: 5
3 Correct 1 ms 364 KB Correct! Number of queries: 23
4 Correct 1 ms 364 KB Correct! Number of queries: 28
5 Correct 1 ms 364 KB Correct! Number of queries: 32
6 Correct 2 ms 364 KB Correct! Number of queries: 35
7 Correct 7 ms 364 KB Correct! Number of queries: 400
8 Correct 4 ms 396 KB Correct! Number of queries: 400
9 Correct 5 ms 364 KB Correct! Number of queries: 400
10 Correct 7 ms 364 KB Correct! Number of queries: 400
11 Correct 6 ms 364 KB Correct! Number of queries: 300
12 Correct 6 ms 512 KB Correct! Number of queries: 400
13 Correct 6 ms 364 KB Correct! Number of queries: 300
14 Correct 7 ms 364 KB Correct! Number of queries: 400
15 Correct 7 ms 364 KB Correct! Number of queries: 400
16 Correct 8 ms 364 KB Correct! Number of queries: 400

Subtask #3
48.230749 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 368 KB Correct! Number of queries: 32
2 Correct 1 ms 364 KB Correct! Number of queries: 5
3 Correct 1 ms 364 KB Correct! Number of queries: 23
4 Correct 1 ms 364 KB Correct! Number of queries: 28
5 Correct 1 ms 364 KB Correct! Number of queries: 32
6 Correct 2 ms 364 KB Correct! Number of queries: 35
7 Correct 7 ms 364 KB Correct! Number of queries: 400
8 Correct 4 ms 396 KB Correct! Number of queries: 400
9 Correct 5 ms 364 KB Correct! Number of queries: 400
10 Correct 7 ms 364 KB Correct! Number of queries: 400
11 Correct 6 ms 364 KB Correct! Number of queries: 300
12 Correct 6 ms 512 KB Correct! Number of queries: 400
13 Correct 6 ms 364 KB Correct! Number of queries: 300
14 Correct 7 ms 364 KB Correct! Number of queries: 400
15 Correct 7 ms 364 KB Correct! Number of queries: 400
16 Correct 8 ms 364 KB Correct! Number of queries: 400
17 Correct 107 ms 1116 KB Correct! Number of queries: 2500
18 Correct 93 ms 1028 KB Correct! Number of queries: 2200
19 Correct 105 ms 820 KB Correct! Number of queries: 2200
20 Correct 103 ms 912 KB Correct! Number of queries: 2500
21 Correct 101 ms 936 KB Correct! Number of queries: 2300
22 Correct 102 ms 876 KB Correct! Number of queries: 2200
23 Correct 98 ms 796 KB Correct! Number of queries: 2200
24 Correct 108 ms 932 KB Correct! Number of queries: 2500
25 Correct 106 ms 928 KB Correct! Number of queries: 2500
26 Correct 120 ms 876 KB Correct! Number of queries: 2500