Submission #899075

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
899075	2024-01-05T13:05:24 Z	jamjanek	Ancient Machine 2 (JOI23_ancient2)	C++17	37 / 100	78 ms	1580 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	43 ms	832 KB	Output is partially correct
2	Partially correct	37 ms	820 KB	Output is partially correct
3	Partially correct	41 ms	820 KB	Output is partially correct
4	Partially correct	40 ms	564 KB	Output is partially correct
5	Partially correct	41 ms	1068 KB	Output is partially correct
6	Partially correct	38 ms	1560 KB	Output is partially correct
7	Partially correct	40 ms	1076 KB	Output is partially correct
8	Partially correct	40 ms	816 KB	Output is partially correct
9	Partially correct	37 ms	832 KB	Output is partially correct
10	Partially correct	78 ms	1316 KB	Output is partially correct
11	Partially correct	38 ms	1072 KB	Output is partially correct
12	Partially correct	37 ms	824 KB	Output is partially correct
13	Partially correct	37 ms	804 KB	Output is partially correct
14	Partially correct	42 ms	1056 KB	Output is partially correct
15	Partially correct	42 ms	1072 KB	Output is partially correct
16	Partially correct	47 ms	808 KB	Output is partially correct
17	Partially correct	46 ms	1080 KB	Output is partially correct
18	Partially correct	37 ms	816 KB	Output is partially correct
19	Partially correct	41 ms	1064 KB	Output is partially correct
20	Partially correct	38 ms	1072 KB	Output is partially correct
21	Partially correct	40 ms	1316 KB	Output is partially correct
22	Partially correct	40 ms	812 KB	Output is partially correct
23	Partially correct	38 ms	1068 KB	Output is partially correct
24	Partially correct	37 ms	832 KB	Output is partially correct
25	Partially correct	40 ms	804 KB	Output is partially correct
26	Partially correct	41 ms	1216 KB	Output is partially correct
27	Partially correct	39 ms	592 KB	Output is partially correct
28	Partially correct	48 ms	716 KB	Output is partially correct
29	Partially correct	40 ms	1068 KB	Output is partially correct
30	Partially correct	37 ms	816 KB	Output is partially correct
31	Partially correct	38 ms	1064 KB	Output is partially correct
32	Partially correct	39 ms	1048 KB	Output is partially correct
33	Partially correct	39 ms	812 KB	Output is partially correct
34	Partially correct	37 ms	812 KB	Output is partially correct
35	Partially correct	38 ms	1308 KB	Output is partially correct
36	Partially correct	37 ms	1064 KB	Output is partially correct
37	Partially correct	40 ms	1076 KB	Output is partially correct
38	Partially correct	41 ms	1572 KB	Output is partially correct
39	Partially correct	44 ms	1248 KB	Output is partially correct
40	Partially correct	44 ms	1104 KB	Output is partially correct
41	Partially correct	41 ms	1080 KB	Output is partially correct
42	Partially correct	39 ms	808 KB	Output is partially correct
43	Partially correct	38 ms	808 KB	Output is partially correct
44	Partially correct	44 ms	1060 KB	Output is partially correct
45	Partially correct	41 ms	1544 KB	Output is partially correct
46	Partially correct	39 ms	1316 KB	Output is partially correct
47	Partially correct	39 ms	1072 KB	Output is partially correct
48	Partially correct	50 ms	1568 KB	Output is partially correct
49	Partially correct	46 ms	1032 KB	Output is partially correct
50	Partially correct	47 ms	828 KB	Output is partially correct
51	Partially correct	39 ms	824 KB	Output is partially correct
52	Partially correct	39 ms	812 KB	Output is partially correct
53	Partially correct	45 ms	1072 KB	Output is partially correct
54	Partially correct	39 ms	1064 KB	Output is partially correct
55	Partially correct	46 ms	1580 KB	Output is partially correct
56	Partially correct	40 ms	1332 KB	Output is partially correct
57	Partially correct	43 ms	1320 KB	Output is partially correct
58	Partially correct	40 ms	1324 KB	Output is partially correct
59	Partially correct	40 ms	1316 KB	Output is partially correct
60	Partially correct	46 ms	812 KB	Output is partially correct
61	Partially correct	41 ms	1328 KB	Output is partially correct
62	Partially correct	50 ms	1064 KB	Output is partially correct
63	Partially correct	41 ms	1320 KB	Output is partially correct