# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
986692 | PurpleCrayon | Ancient Machine 2 (JOI23_ancient2) | C++17 | 71 ms | 1100 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
mt19937 rng(69);
int rnd(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
int qry(vector<int> v) {
int m = 2 * sz(v);
vector<int> a(m), b(m);
for (int i = 0; i < m; i++) {
int par = i % 2, c = i / 2;
a[i] = ((c + 1) % sz(v)) * 2 + par;
if (v[c]) {
b[i] = ((c + 1) % sz(v)) * 2 + (par ^ 1);
} else {
b[i] = a[i];
}
}
return Query(m, a, b) % 2;
}
string Solve(int N) {
const int p = 57;
const int n = 1e3;
assert(n == N);
bitset<n> b[n]; // basis
int who[n];
for (int i = 0; i < n; i++) b[i] = 0;
int cnt = 0;
while (cnt < n) {
int x = rnd(1, p);
vector<int> use(x);
for (int i = 0; i < x; i++) use[i] = rnd(0, 1);
bitset<n> cur;
int my_who = 0;
for (int i = 0; i < n; i++) cur[i] = use[i % x];
for (int i = 0; i < n; i++) if (cur[i]) {
if (b[i].any()) {
cur ^= b[i];
my_who ^= who[i];
} else {
b[i] = cur;
who[i] = my_who ^= qry(use);
cnt++;
break;
}
}
}
string s;
for (int i = 0; i < n; i++) {
int ans = 0;
bitset<n> cur; cur[i] = 1;
for (int j = 0; j < n; j++) if (cur[j]) {
cur ^= b[j];
ans ^= who[j];
}
s += char('0' + ans);
}
return s;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |