Submission #369869

#	Time	Username	Problem	Language	Result	Execution time	Memory
369869		doowey	Mouse (info1cup19_mouse)	C++14	99.23 / 100	120 ms	1116 KiB

mouse

#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 (stderr)

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 / 13
• Subtask 2: 38 / 38
• Subtask 3: 48.230748999999996 / 49