Submission #832972

#	Time	Username	Problem	Language	Result	Execution time	Memory
832972		doowey	Ancient Machine 2 (JOI23_ancient2)	C++17	97 / 100	36 ms	660 KiB

ancient2

#include "ancient2.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace {

int variable_example = 1;

}  // namespace


const int M = 100;
const int N = 1002;
bitset<N> eq[N]; // 0111011[1] = x1 + x2 + x3 + x5 + x6 = x[n+1]
bool has[N];
bitset<N> cur;
int n;
int id;

bool add(){
	for(int i = n - 1; i >= 0 ; i -- ){
		if(cur[i]){
			if(has[i]){
				cur ^= eq[i];
			}
			else{
				
				eq[i]=cur;
				has[i]=true;
				id = i;
				return true;
			}
		}
	}
	return false;
}

string Solve(int _n) {
	n = _n;
	string s;
	for(int i = 0 ; i < n; i ++ ){
		s.push_back('0');
	}
	id = 0;
	int total = 0;
	for(int mod = 1; mod < M; mod ++ ){
		
		for(int x = 0; x < mod ; x ++ ){
			cur.reset();
			for(int y = x; y < n; y += mod){
				cur[y]=1;
			}
			if(add()){
				total ++ ;
				vector<int> qa(mod * 2), qb(mod * 2);
				for(int i = 0 ; i < mod; i ++ ){
					qa[i] = (i + 1) % mod;
					qb[i] = (i + 1) % mod;
					
					qa[i + mod] = (i + 1) % mod + mod;
					qb[i + mod] = (i + 1) % mod + mod; // sooo we want to flip side when we arrive at i mod 
					if(i == x){
						swap(qb[i], qb[i + mod]);
					}
				}
				int send = Query(mod * 2, qa, qb);
				if(send >= mod){
					eq[id].flip(n);
				}
				if(total == n) break;
			}
		}
		if(total == n) break;
	} 
	
	for(int i = 0 ; i < n; i ++ ){
		for(int j = 0 ; j < i ; j ++ ){
			if(eq[i][j]) eq[i] ^= eq[j];
		}
		if(eq[i][n]) s[i] ++ ;
	}
	return s;
}

Compilation message (stderr)

ancient2.cpp:18:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   18 | int variable_example = 1;
      |     ^~~~~~~~~~~~~~~~

• Subtask 1: 97 / 100