Submission #1015051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015051		oolimry	Mouse (info1cup19_mouse)	C++17	100 / 100	63 ms	600 KiB

mouse

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint,lint> ii;

int solved[260];

void solve(int n) {
  srand(time(NULL));
  vector<int> best;
  for(int i = 1; i <= n; i++) best.push_back(i);

  while(true){
    random_shuffle(all(best));
    if(query(best) == 0) break;
  }

  vector<int> unknown;


  int cur = 0;

  int known = -1;
  while(true){
    unknown.clear();
    for(int i = 0; i < n; i++){
      if(not solved[i]) unknown.push_back(i);
      else known = i;
    }
    random_shuffle(all(unknown));
    vector<int> test;
    for(int x : best) test.push_back(x);

    for(int i = 0;i+1 < sz(unknown);i += 2){
      swap(test[unknown[i]], test[unknown[i+1]]);
    }

    int nxt = query(test);
    if(nxt == n) return;
    if(nxt == cur) continue;

    if(nxt > cur){
      //cout << "U: "; for(int x : unknown) cout << x << " "; cout << endl;
      ////cout << "P: "; for(int i = 0;i < n;i++) cout << i << " "; cout << endl;
      //cout << "B: "; for(int x : best) cout << x << " "; cout << endl;
      int low = -1; int high = sz(unknown)/2 - 1;

      while(low != high-1){
        int mid = (low+high)/2;
        test.clear(); for(int x : best) test.push_back(x);
        for(int i = 0;i <= mid;i++){
          swap(test[unknown[i*2]], test[unknown[i*2+1]]);
        }

        int res = query(test);
        if(res == n) return;
        if(res > cur) high = mid;
        else low = mid;
      }


      int a = unknown[high*2], b = unknown[high*2+1];
      swap(best[a], best[b]);
      int newcur = query(best);
      if(newcur == n) return;

      if(newcur - cur == 2){
        solved[a] = 1;
        solved[b] = 1;
      }
      else{
        if(known == -1){
          int x = 1;
          while(x == a or x == b) x++;

          vector<int> test; for(int x : best) test.push_back(x);
          swap(test[x], test[a]);
          if(query(test) < newcur) solved[a] = 1;
          else solved[b] = 1;
        }
        else{
          vector<int> test; for(int x : best) test.push_back(x);
          swap(test[known], test[a]);

          if(query(test) == newcur-1) solved[b] = 1;
          else solved[a] = 1;
        }
      }

      cur = newcur;

    }
  }
}

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