Submission #900076

#	Time	Username	Problem	Language	Result	Execution time	Memory
900076		weajink	Ancient Machine 2 (JOI23_ancient2)	C++17	100 / 100	32 ms	2176 KiB

ancient2

#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//Autor: Michał Szeliga
#ifdef LOCAL
#define debug(...) __VA_ARGS__;
#else
#define debug(...) {}
#endif
#define read(...) debug((void)!freopen(__VA_ARGS__,"r",stdin););
 
const int M = 1001;
bitset<M> akt[M-1];
int ile = 0;
int gauss(bitset<M> x){
	int i;
	for (i = 0; i < M-1; i++){
		if (x[i]){
			if (!akt[i][i]){
				//cout<<i<<" # "<<x<<"\n";
				akt[i] = x;
				ile++;
				return i;
			}
			x ^= akt[i];
		}
	}
	return -1;
}
bool policz(int x){
	bitset<M> wy;
	wy[x] = 1;
	for (int i = 0; i < M-1; i++){
		if (wy[i]) wy ^= akt[i];
	}
	return wy[M-1];
}
void stworz_automat(int c, int r){
	bitset<M> wy;
	for (int i = r; i < M-1; i += c) wy[i] = 1;
	int id = gauss(wy);
	if (id != -1){
		int m = 2*c;
		vector<int> A,B;
		for (int i = 0; i < c; i++){
			if (i%c == r){
				A.push_back((r+1)%c);
				B.push_back(c+(r+1)%c);
			}else{
				A.push_back((i+1)%c);
				B.push_back((i+1)%c);
			}
		}
		for (int i = c; i < 2*c; i++){
			if (i%c == r){
				A.push_back(c+(r+1)%c);
				B.push_back((r+1)%c);
			}else{
				A.push_back(c+(i+1)%c);
				B.push_back(c+(i+1)%c);
			}
		}
		/*cout<<"Zapytanie o "<<c<<" "<<r<<"\n";
		for (int j = 0; j < m; j++){
			cout<<A[j]<<" "<<B[j]<<"\n";
		}*/
		akt[id][M-1] = akt[id][M-1]^(Query(m,A,B) >= c);
		//cout<<id<<" "<<akt[id]<<"\n";
	}
}
void stworz_automat2(int k){
	bitset<M> wy;
	wy[k] = 1;
	vector<int> A,B;
	for (int i = 0; i < k; i++){
		A.push_back(i+1);
		B.push_back(i+1);
	}
	A.push_back(k+1);
	B.push_back(k+2);
	A.push_back(k+1);
	B.push_back(k+1);
	A.push_back(k+2);
	B.push_back(k+2);
	wy[M-1] = (Query(k+3,A,B) > k+1);
	gauss(wy);
}
string sufiks;
void stworz_automat3(int k){
	bitset<M> wy;
	wy[M-k-1] = 1;
	sufiks = '0'+sufiks;
	string s = '#'+sufiks+'$'+sufiks;
//	cout<<s<<"\n";
	int n = s.size();
	int P[n+1];
	P[1] = 0;
	for (int i = 2; i < n; i++){
		int os = P[i-1];
		while (os && s[os+1] != s[i]){
			os = P[os];
		}
		if (s[os+1] == s[i]) os++;
		P[i] = os;
		//cout<<i<<" "<<P[i]<<"\n";
	} 
	vector<int> A,B;
//	cout<<k+1<<"\n";
	for (int i = 0; i < k+1; i++){
		if (i == k || sufiks[i] == '1'){
			int os = P[i+sufiks.size()+1];
			while (os && s[os+1] != '0'){
				os = P[os];
			}
			if (s[os+1] == '0') os++;
			A.push_back(os);
		}
		if (i == k || sufiks[i] == '0'){
			int os = P[i+sufiks.size()+1];
			while (os && s[os+1] != '1'){
				os = P[os];
			}
			if (s[os+1] == '1') os++;
			B.push_back(os);
		}
		if (A.size() < B.size()) A.push_back(i+1);
		if (B.size() < A.size()) B.push_back(i+1);
		//cout<<A.back()<<" "<<B.back()<<"\n";
	}
	//exit(0);
	int x = Query(k+1,A,B);
	//cout<<x<<" "<<k<<"\n";
	wy[M-1] = (x!=k);
	//if (k == 4) exit(0);
	if (wy[M-1] == 1) sufiks[0] = '1';
	gauss(wy);
}
string Solve(int n){
	for (int i = 0; i < 100; i++) stworz_automat2(i);
	for (int i = 1; i <= 100; i++) stworz_automat3(i);
	for (int c = 1; c < M-1; c++){
		for (int r = 0; r < c; r++){
			stworz_automat(c,r);
			if (ile == M-1) break;
		}
	} 
	string wy;
	for (int i = 0; i < n; i++){
		if (policz(i)) wy += '1';
		else wy += '0';
	}
	return wy;
}

• Subtask 1: 100 / 100