| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 815200 | 2023-08-08T13:08:52 Z | minhcool | Ancient Machine 2 (JOI23_ancient2) | C++17 | 0 ms | 0 KB |
//#define local
#ifndef local
#include "ancient2.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
int n;
bitset<1005> basis[1005];
bool vis[1005];
bool ck[1005];
bool ckk(int p, int q){
int m = 2 * p;
vector<int> vc1(m), vc2(m);
for(int i = 0; i < 2 * m; i++) vc1[i] = i + 1;
vc1[2 * m - 1] = m, vc1[m - 1] = 0;
vc2 = vc1;
vc2[q] = p + q + 1, vc2[p + q] = q + 1;
int temp = Query(m, vc1, vc2);
return (temp >= p);
}
int in(bitset<1005> bts){
bool temp = 0;
for(int i = 0; i < 1000; i++){
if(!bts[i]) continue;
if(!vis[i]){
vis[i] = 1;
ck[i] = temp;
basis[i] = bts;
return i;
}
bts ^= basis[i];
temp ^= ck[i];
}
return -1;
}
int cal(bitset<1005> bts){
bool ans = 0;
for(int i = 0; i < 1000; i++){
if(!bts[i]) continue;
bts ^= basis[i];
ans ^= ck[i];
}
return ans;
}
string s;
string Solve(int N){
n = N;
s.resize(n);
int p = 55;
for(int itr = 0; itr < 100; itr++){
vector<int> a(itr + 3), b(itr + 3);
for(int i = 0; i < itr; i++) a[i] = b[i] = i + 1;
a[itr] = itr + 1;
b[itr] = itr + 2;
a[itr + 1] = b[itr + 1] = itr + 1;
a[itr + 2] = b[itr + 2] = itr + 2;
int temp = Query(itr + 2, a, b);
if(temp == itr + 1) s[itr1] = '0';
else s[itr] = '1';
}
for(int itr = 100; itr < 200; itr++){
vector<int> a(101), b(101);
for(int i = 0; i < 99; i++) a[i] = b[i] = i + 1;
a[99] = b[99] = 0;
if(s[itr - 100] == '0') b[itr - 100] = 100;
else a[itr - 100] = 100;
a[100] = b[100] = 100;
int temp = Query(101, a, b);
if(temp == 100) s[itr] = char(97 - s[itr - 100]);
else s[itr] = s[itr - 100];
}
for(int itr = 0; itr < 200; itr++){
bitset<1005> bts;
for(int i = 0; i <= 1000; i++) bts[i] = 0;
bts[itr] = 1;
int pos = in(bts);
if(pos < 0) continue;
if(s[itr] == '1') ck[itr] ^= 1;
}
for(int l = 1; l <= 55; l++){
for(int r = 0; r < l; r++){
bitset<1005> bts;
for(int i = 0; i <= 1000; i++) bts[i] = 0;
for(int i = r; i <= 1000; i += l) bts[i] = 1;
int temp = in(bts);
if(temp < 0) continue;
bool temp2 = ckk(l, r);
ck[temp] ^= temp2;
}
}
for(int i = 201; i < 1000; i++){
bitset<1005> bts;
bts[i] = 1;
s[i] = char(48 + cal(bts));
}
return s;
}
#ifdef local
void process(){
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) process();
}
#endif