#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll inf = 1e18;
ll K = 5001;
vector<vector<int>> devise_strategy(int n) {
vector<vector<int>> s(32, vector<int>(n + 1));
for (int val = 0; val < 32; val++) {
if (val % 4 == 0) {
s[val][0] = 0;
for (int x = 1; x <= n; x++) {
int l = 1, r = K;
int done = val / 4;
for (int i = 0; i < done + 1; i++) {
int mid1 = (2*l + r) / 3;
int mid2 = (l + 2*r) / 3;
if (i == done) {
if (x < mid1) {
s[val][x] = 4 * done + 1;
} else if (x < mid2) {
s[val][x] = 4 * done + 2;
} else {
s[val][x] = 4 * done + 3;
}
} else {
if (x < mid1) {
r = mid1;
} else if (x < mid2) {
l = mid1;
r = mid2;
} else {
l = mid2;
}
}
}
}
} else {
s[val][0] = 1;
for (int x = 1; x <= n; x++) {
int l = 1, r = K;
int done = val / 4;
int typ = val % 4;
s[val][x] = (done + 1) * 4 % 32;
for (int i = 0; i < done + 1; i++) {
int mid1 = (2*l + r) / 3;
int mid2 = (l + 2*r) / 3;
if (i == done) {
if (x < mid1) {
if (typ > 1) {
s[val][x] = -2;
}
} else if (x < mid2) {
if (typ == 1) {
s[val][x] = -1;
} else if (typ == 3) {
s[val][x] = -2;
}
} else {
if (typ < 3) {
s[val][x] = -1;
}
}
} else {
if (x < mid1) {
r = mid1;
} else if (x < mid2) {
l = mid1;
r = mid2;
} else {
l = mid2;
}
}
}
}
}
}
return s;
}
/*
bool judge(int a, int b) {
auto s = devise_strategy(K - 1);
int cur = 0;
set<int> st;
while (cur >= 0) {
if (st.find(cur) != st.end()) {
cout << "CYCLING? NUMBER " << cur << " ON CASE " << a << ' ' << b << endl;
exit(0);
}
st.insert(cur);
int val = a;
if (s[cur][0] == 1) {
val = b;
}
cur = s[cur][val];
}
if (cur == -1) {
return a < b;
} else {
return a > b;
}
}
signed main() {
auto s = devise_strategy(K - 1);
for (int i = 0; i < 10000; i++) {
int a = rnd() % (K - 1) + 1;
int b = rnd() % (K - 1) + 1;
while (a == b) {
b = rnd() % (K - 1) + 1;
}
if (!judge(a, b)) {
cout << "FAIL ON " << a << ' ' << b << endl;
return 0;
}
if (i % 200 == 99) {
cout << "SUCCESS" << endl;
}
}
cout << "TOTAL SUCCESS" << endl;
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |