Submission #963675

#	Time	Username	Problem	Language	Result	Execution time	Memory
963675		Trisanu_Das	Ancient Machine 2 (JOI23_ancient2)	C++17	97 / 100	33 ms	2056 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); 
 
 
const int M = 100;
const int N = 1002;
bitset<N> eq[N];
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; 
					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;
}

• Subtask 1: 97 / 100