# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1103224 | horiaboeriu | Mouse (info1cup19_mouse) | C++17 | 0 ms | 0 KiB |
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>
#include "grader.h"
using namespace std;
const int MAXN = 256;
const int MOD = 2007;
int v[MAXN + 1], vrez[MAXN];
map<int, map<int, int>> cand;
map<int, int> fr;
map<int, int>::iterator it;
int rez2;
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);
}
int query(vector<int> q) {
int i, nr, nr2;
nr = q.size();
nr2 = 0;
for (i = 0; i < nr; i++) {
nr2 += (q[i] == vrez[i]);
}
return nr2;
}
void solve(int n) {
int i, j, x, rez;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
cand[i][j] = 1;
}
}
vector<int> q;
for (i = 1; i <= n; i++) {
while ((int)cand[i].size() > 1) {
fr.clear();
for (j = 1; j <= n; j++) {
fr[j] = 1;
}
q.clear();
for (j = 1; j < i; j++) {
q.push_back(v[j]);
fr.erase(v[j]);
}
x = genrand() % n + 1;
it = cand[i].lower_bound(x);
if (it == cand[i].end()) {
it--;
}
q.push_back(it->first);//candidat random
fr.erase(q[i - 1]);
//in q sunt indexate de la 0
for (j = i + 1; j <= n; j++) {
x = genrand() % n + 1;
it = fr.lower_bound(x);
if (it == fr.end()) {
it--;
}
x = it->first;
q.push_back(x);
fr.erase(x);
}
rez = query(q);
rez2++;
if (rez == i - 1) {
//nu sunt pe pozitiile bune cei de la i la n
for (j = i; j <= n; j++) {
cand[j].erase(q[j - 1]);
}
} else if (rez == n) {
return;
}
}
it = cand[i].begin();
v[i] = it->first;
for (j = i + 1; j <= n; j++) {
cand[j].erase(v[i]);
}
}
}