oj.uz

Submission #1015051

# Submission time Handle Problem Language Result Execution time Memory
1015051 2024-07-06T03:48:54 Z oolimry Mouse (info1cup19_mouse) C++17
100 / 100
 63 ms 600 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct! Number of queries: 32
2 Correct 0 ms 344 KB Correct! Number of queries: 13
3 Correct 0 ms 344 KB Correct! Number of queries: 21
4 Correct 1 ms 344 KB Correct! Number of queries: 26
5 Correct 0 ms 344 KB Correct! Number of queries: 26
6 Correct 0 ms 344 KB Correct! Number of queries: 18

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct! Number of queries: 32
2 Correct 0 ms 344 KB Correct! Number of queries: 13
3 Correct 0 ms 344 KB Correct! Number of queries: 21
4 Correct 1 ms 344 KB Correct! Number of queries: 26
5 Correct 0 ms 344 KB Correct! Number of queries: 26
6 Correct 0 ms 344 KB Correct! Number of queries: 18
7 Correct 4 ms 344 KB Correct! Number of queries: 400
8 Correct 2 ms 344 KB Correct! Number of queries: 400
9 Correct 3 ms 340 KB Correct! Number of queries: 300
10 Correct 4 ms 344 KB Correct! Number of queries: 400
11 Correct 2 ms 344 KB Correct! Number of queries: 300
12 Correct 2 ms 344 KB Correct! Number of queries: 300
13 Correct 3 ms 344 KB Correct! Number of queries: 300
14 Correct 3 ms 344 KB Correct! Number of queries: 400
15 Correct 3 ms 344 KB Correct! Number of queries: 400
16 Correct 4 ms 344 KB Correct! Number of queries: 400

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct! Number of queries: 32
2 Correct 0 ms 344 KB Correct! Number of queries: 13
3 Correct 0 ms 344 KB Correct! Number of queries: 21
4 Correct 1 ms 344 KB Correct! Number of queries: 26
5 Correct 0 ms 344 KB Correct! Number of queries: 26
6 Correct 0 ms 344 KB Correct! Number of queries: 18
7 Correct 4 ms 344 KB Correct! Number of queries: 400
8 Correct 2 ms 344 KB Correct! Number of queries: 400
9 Correct 3 ms 340 KB Correct! Number of queries: 300
10 Correct 4 ms 344 KB Correct! Number of queries: 400
11 Correct 2 ms 344 KB Correct! Number of queries: 300
12 Correct 2 ms 344 KB Correct! Number of queries: 300
13 Correct 3 ms 344 KB Correct! Number of queries: 300
14 Correct 3 ms 344 KB Correct! Number of queries: 400
15 Correct 3 ms 344 KB Correct! Number of queries: 400
16 Correct 4 ms 344 KB Correct! Number of queries: 400
17 Correct 63 ms 344 KB Correct! Number of queries: 2400
18 Correct 52 ms 344 KB Correct! Number of queries: 2200
19 Correct 50 ms 344 KB Correct! Number of queries: 2200
20 Correct 44 ms 344 KB Correct! Number of queries: 2300
21 Correct 42 ms 344 KB Correct! Number of queries: 2300
22 Correct 51 ms 344 KB Correct! Number of queries: 2300
23 Correct 49 ms 600 KB Correct! Number of queries: 2300
24 Correct 55 ms 344 KB Correct! Number of queries: 2400
25 Correct 47 ms 344 KB Correct! Number of queries: 2300
26 Correct 46 ms 344 KB Correct! Number of queries: 2300