oj.uz

Submission #1103349

# Submission time Handle Problem Language Result Execution time Memory
1103349 2024-10-20T17:10:38 Z matthew Mouse (info1cup19_mouse) C++17
80.9231 / 100
 378 ms 3408 KB 
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int modul(int a) {
  return a < 0 ? -a : a;
}
static inline unsigned long long genrand() {
  int x = modul((int)(uniform_int_distribution<unsigned long long>(0, (unsigned long long)-1)(rng) * 35023 % 1621931));
  return x;
}
 
const int MAX_N = 256;
 
// candidates[i] = ce numere pot sa apara pe pozitia i
std::set<int> candidates[MAX_N];
int perm[MAX_N];
char vis[MAX_N];
int order[MAX_N];
 
#ifdef LOCAL
int query(std::vector<int> guess);
#endif

void init_candidates(int n) {
  for(int i = 0; i < n; i++) {
    candidates[i].clear();
    int indian = genrand() % n;
    for(int j = 0; j < n; j++) {
      candidates[i].insert(j);
    }
  }
}

#ifdef LOCAL
int n, qs;
std::vector<int> x;
#endif
bool is_perm(int n) {
  std::vector<int> p;
  p.clear();
  for(int i = 0; i < n; i++) {
    p.push_back(perm[i]);
  }
  std::sort(p.begin(), p.end());
  for(int i = 0; i < n; i++) {
    if(p[i] != i) {
      return false;
    }
  }
  return true;
}

int ask(int n) {
  assert(is_perm(n));
  std::vector<int> guess;
  for(int i = 0; i < n; i++) {
    guess.push_back(perm[order[i]] + 1);
  }
  int ans = query(guess);
  if(ans == n) {
    exit(0); // heheheha
  } else {
    return ans;
  }
}
 
int get_rand_from_set(std::set<int> s) {
  int size = s.size();
  int pos = genrand() % size;
  auto it = s.begin();
  std::advance(it, pos);
  return *it;
}
 
void find_permutation(int n) {
  for(int i = 0; i < n; i++) {
    assert(candidates[i].size() > 0);
    while(candidates[i].size() > 1) {
      // completam pozitiile i..n-1
      perm[i] = get_rand_from_set(candidates[i]);
      for(int j = 0; j < n; j++) {
        vis[j] = 0;
      }
      for(int j = 0; j <= i; j++) {
        vis[perm[j]] = 1;
      }
      for(int j = i + 1; j < n; j++) {
        int remaining = n - j;
        int idx = 0;
        int r = genrand();
        int pos = r % remaining;
        for(int k = 0; k <= pos; k++) {
          while(idx < n && vis[idx]) {
            idx++;
          }
          if(k < pos) {
            idx++;
          }
        }
        perm[j] = idx;
        vis[idx] = 1;
      }
      int q = ask(n);
      if(q == i) {
        for(int j = i; j < n; j++) {
          candidates[j].erase(perm[j]);
        }
      }
    }
    perm[i] = *candidates[i].begin();
    for(int j = i + 1; j < n; j++) {
      candidates[j].erase(perm[i]);
    }
  }
}
 
void solve(int n) {
  for(int i = 0; i < n; i++) {
    order[i] = i;
  }
  shuffle(order, order + n, rng);
  srand(time(0));
  init_candidates(n);
  find_permutation(n);
  int xx = ask(n);
  assert(xx == n);
}

#ifdef LOCAL
int main() {
  scanf("%d", &n);
 
  for(int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    x.push_back(a);
  }
 
  qs = 0;
  solve(n);
 
  return 0;
}
int query(std::vector<int> guess) {
  qs++;
  int cnt = 0;
  for(int i = 0; i < n; i++) {
    cnt += (guess[i] == x[i]);
  }
  printf("answer %d for query %d:\n", cnt, qs);
  for(int i = 0; i < n; i++) {
    printf("%d ", guess[i]);
  }
  printf("\n");
  return cnt;
}
#endif

Compilation message

mouse.cpp: In function 'void init_candidates(int)':
mouse.cpp:29:9: warning: unused variable 'indian' [-Wunused-variable]
   29 |     int indian = genrand() % n;
      |         ^~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct! Number of queries: 26
2 Correct 1 ms 336 KB Correct! Number of queries: 3
3 Correct 1 ms 336 KB Correct! Number of queries: 19
4 Correct 1 ms 336 KB Correct! Number of queries: 36
5 Correct 1 ms 336 KB Correct! Number of queries: 35
6 Correct 1 ms 336 KB Correct! Number of queries: 31

Subtask #2
31.99999 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct! Number of queries: 26
2 Correct 1 ms 336 KB Correct! Number of queries: 3
3 Correct 1 ms 336 KB Correct! Number of queries: 19
4 Correct 1 ms 336 KB Correct! Number of queries: 36
5 Correct 1 ms 336 KB Correct! Number of queries: 35
6 Correct 1 ms 336 KB Correct! Number of queries: 31
7 Correct 10 ms 336 KB Correct! Number of queries: 600
8 Correct 10 ms 336 KB Correct! Number of queries: 600
9 Correct 10 ms 504 KB Correct! Number of queries: 600
10 Correct 9 ms 336 KB Correct! Number of queries: 600
11 Correct 7 ms 500 KB Correct! Number of queries: 500
12 Correct 9 ms 336 KB Correct! Number of queries: 600
13 Correct 9 ms 336 KB Correct! Number of queries: 500
14 Correct 13 ms 336 KB Correct! Number of queries: 600
15 Correct 11 ms 336 KB Correct! Number of queries: 600
16 Correct 12 ms 336 KB Correct! Number of queries: 600

Subtask #3
35.923076 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct! Number of queries: 26
2 Correct 1 ms 336 KB Correct! Number of queries: 3
3 Correct 1 ms 336 KB Correct! Number of queries: 19
4 Correct 1 ms 336 KB Correct! Number of queries: 36
5 Correct 1 ms 336 KB Correct! Number of queries: 35
6 Correct 1 ms 336 KB Correct! Number of queries: 31
7 Correct 10 ms 336 KB Correct! Number of queries: 600
8 Correct 10 ms 336 KB Correct! Number of queries: 600
9 Correct 10 ms 504 KB Correct! Number of queries: 600
10 Correct 9 ms 336 KB Correct! Number of queries: 600
11 Correct 7 ms 500 KB Correct! Number of queries: 500
12 Correct 9 ms 336 KB Correct! Number of queries: 600
13 Correct 9 ms 336 KB Correct! Number of queries: 500
14 Correct 13 ms 336 KB Correct! Number of queries: 600
15 Correct 11 ms 336 KB Correct! Number of queries: 600
16 Correct 12 ms 336 KB Correct! Number of queries: 600
17 Correct 378 ms 3408 KB Correct! Number of queries: 3900
18 Correct 305 ms 3152 KB Correct! Number of queries: 3800
19 Correct 329 ms 3152 KB Correct! Number of queries: 3800
20 Correct 340 ms 3408 KB Correct! Number of queries: 3900
21 Correct 322 ms 3152 KB Correct! Number of queries: 3800
22 Correct 326 ms 3152 KB Correct! Number of queries: 3900
23 Correct 306 ms 3152 KB Correct! Number of queries: 4000
24 Correct 334 ms 3408 KB Correct! Number of queries: 3900
25 Correct 321 ms 3408 KB Correct! Number of queries: 3700
26 Correct 331 ms 3408 KB Correct! Number of queries: 4100