Submission #899075

#	Time	Username	Problem	Language	Result	Execution time	Memory
899075		jamjanek	Ancient Machine 2 (JOI23_ancient2)	C++17	37 / 100	78 ms	1580 KiB

ancient2

#include "ancient2.h"
#include<bits/stdc++.h>
using namespace std;

bool prefix(int k){
	int m = k+1+2;
	vector<int>a(m), b(m);
	for(int i=0;i<k;i++){
		a[i] = i+1;
		b[i] = i+1;
	}
	a[k] = k+1;
	b[k] = k+2;
	a[k+2] = k+2;
	b[k+2] = k+2;
	a[k+1] = k+1;
	b[k+1] = k+1;
	return Query(m,a,b)==(k+2);
}

string PoznajSufix(int k){
	string s="2";
	while((int)s.size()-1<k){
		s[0]='0';
		s = '2' + s;
		int m = s.size();
		vector<int>a(m), b(m);
		vector<int>kmp(m);
		kmp[0] = 0;
		kmp[1] = 0;
		for(int i=2;i<m;i++){
			int j = kmp[i-1];
			while(j!=0 && s[j+1]!=s[i])
				j = kmp[j];
			if(s[j+1]==s[i])
				j++;
			kmp[i] = j;
		}
		for(int i=0;i<m-1;i++){
			if(s[i+1]=='0'){
				a[i] = i+1;
				int j = kmp[i];
				while(s[j+1]!='1' && j!=0)j = kmp[j];
				if(s[j+1]=='1')j++;
				b[i] = j;
			}
			else if(s[i+1]=='1'){
				int j = kmp[i];
				while(s[j+1]!='0' && j!=0)j = kmp[j];
				if(s[j+1]=='0')j++;
				a[i] = j;
				b[i] = i+1;
			}
		}
		int j = kmp[m-1];
		while(s[j+1]!='0' && j!=0)j = kmp[j];
		if(s[j+1]=='0')j++;
		a[m-1] = j;

		j = kmp[m-1];
		while(s[j+1]!='1' && j!=0)j = kmp[j];
		if(s[j+1]=='1')j++;
		b[m-1] = j;
		if(Query(m, a, b)!=m-1)
			s[1] = '1';
	}
	reverse(s.begin(), s.end());s.pop_back();reverse(s.begin(), s.end());
	return s;
}

string Solve(int N) {
	
	string s;
	while((int)s.size()<N/2){
		s.push_back('0'+prefix(s.size()));
	}
	string sufix;
	sufix = PoznajSufix((N+1)/2);
//	cout<<sufix<<"\n";
	return s+sufix;
}

• Subtask 1: 37 / 100