Submission #370250

#	Time	Username	Problem	Language	Result	Execution time	Memory
370250		doowey	Mouse (info1cup19_mouse)	C++14	100 / 100	91 ms	1004 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];

vector<pii> cac;

int bins(int l, int r, int know){
    vector<int> perm = diff;
    for(int j = l ; j <= r; j ++ ){
        swap(perm[cac[j].fi],perm[cac[j].se]);
    }
    int sol = know;
    if(know == -1){
        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, -1);
        bins(mid + 1, r, sol - xa);
    }
    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, -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 (stderr)

mouse.cpp: In function 'void solve(int)':
mouse.cpp:93:13: warning: unused variable 'go' [-Wunused-variable]
   93 |         int go;
      |             ^~
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:68:9: warning: unused variable 'm' [-Wunused-variable]
   68 |     int m;
      |         ^
mouse.cpp:69:9: warning: unused variable 'nx' [-Wunused-variable]
   69 |     int nx;
      |         ^~
mouse.cpp:70:9: warning: unused variable 'li' [-Wunused-variable]
   70 |     int li;
      |         ^~

• Subtask 1: 13 / 13
• Subtask 2: 38 / 38
• Subtask 3: 49 / 49