This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
static inline unsigned long long genrand() {
return uniform_int_distribution<unsigned long long>(0, (unsigned long long)-1)(rng);
}
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];
#ifdef LOCAL
int query(std::vector<int> guess);
#endif
void init_candidates(int n) {
for(int i = 0; i < n; i++) {
candidates[i].clear();
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[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) {
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
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |