QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#409563	#6774. Ancient Machine 2	JohnAlfnov	37	57ms	4212kb	C++20	1.2kb	2024-05-12 11:14:47	2024-05-12 11:14:47

Judging History

你现在查看的是最新测评结果

[2024-05-12 11:14:47]
评测

测评结果：37
用时：57ms
内存：4212kb

查看

[2024-05-12 11:14:47]
提交

answer

#include<bits/stdc++.h>
#include "ancient2.h"
using namespace std;
int an[1005];
int ss[1005],nxt[1005];
string Solve(int N){
	for(int i=1;i<=500;++i){
		vector<int>A;
		vector<int>B;
		for(int j=0;j<i-1;++j){
			A.emplace_back(j+1);
			B.emplace_back(j+1);
		}
		A.emplace_back(i);B.emplace_back(i+1);
		A.emplace_back(i);B.emplace_back(i);
		A.emplace_back(i+1);B.emplace_back(i+1);
		int x=Query(i+2,A,B);
		if(x==i)an[i]=0;
		else an[i]=1;
	}
	for(int i=N;i>N-500;--i){
		int l=N-i+1;
		for(int j=1;j<=l;++j){
			if(j==1)ss[j]=0;
			else ss[j]=an[i+j-1];
		}
		nxt[1]=0;
		for(int j=2;j<=l;++j){
			int r=nxt[j-1];
			while(r&&ss[r+1]!=ss[j])r=nxt[r];
			if(ss[r+1]==ss[j])nxt[j]=r+1;
			else nxt[j]=0;
		}
		vector<int>A,B;
		for(int j=0;j<=l;++j){
			int n0=0,n1=0;
			if(j<l&&ss[j+1]==0)n0=j+1;
			else{
				int r=nxt[j];
				while(r&&ss[r+1]!=0)r=nxt[r];
				if(ss[r+1]==0)n0=r+1;
				else n0=0;
			}
			if(j<l&&ss[j+1]==1)n1=j+1;
			else{
				int r=nxt[j];
				while(r&&ss[r+1]!=1)r=nxt[r];
				if(ss[r+1]==1)n1=r+1;
				else n1=0;
			}
			A.emplace_back(n0);
			B.emplace_back(n1);
		}
		int x=Query(l+1,A,B);
		if(x==l)an[i]=0;
		else an[i]=1;
	}
	string st;
	for(int i=1;i<=N;++i)st+=an[i]+'0';
	return st;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 37

Acceptable Answer

Test #1:

score: 37

Acceptable Answer

time: 30ms

memory: 4208kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #2:

score: 37

Acceptable Answer

time: 21ms

memory: 4212kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #3:

score: 37

Acceptable Answer

time: 19ms

memory: 4168kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #4:

score: 37

Acceptable Answer

time: 27ms

memory: 3972kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #5:

score: 37

Acceptable Answer

time: 20ms

memory: 3892kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #6:

score: 37

Acceptable Answer

time: 22ms

memory: 3928kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #7:

score: 37

Acceptable Answer

time: 29ms

memory: 3912kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #8:

score: 37

Acceptable Answer

time: 25ms

memory: 3904kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #9:

score: 37

Acceptable Answer

time: 15ms

memory: 4200kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #10:

score: 37

Acceptable Answer

time: 57ms

memory: 3988kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #11:

score: 37

Acceptable Answer

time: 28ms

memory: 4204kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #12:

score: 37

Acceptable Answer

time: 28ms

memory: 3920kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #13:

score: 37

Acceptable Answer

time: 26ms

memory: 3920kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #14:

score: 37

Acceptable Answer

time: 29ms

memory: 3920kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #15:

score: 37

Acceptable Answer

time: 21ms

memory: 3912kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #16:

score: 37

Acceptable Answer

time: 32ms

memory: 3884kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #17:

score: 37

Acceptable Answer

time: 31ms

memory: 3948kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #18:

score: 37

Acceptable Answer

time: 27ms

memory: 3988kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #19:

score: 37

Acceptable Answer

time: 26ms

memory: 4200kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #20:

score: 37

Acceptable Answer

time: 26ms

memory: 3920kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #21:

score: 37

Acceptable Answer

time: 30ms

memory: 3904kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #22:

score: 37

Acceptable Answer

time: 27ms

memory: 4196kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #23:

score: 37

Acceptable Answer

time: 21ms

memory: 3908kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #24:

score: 37

Acceptable Answer

time: 20ms

memory: 4204kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #25:

score: 37

Acceptable Answer

time: 23ms

memory: 3916kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #26:

score: 37

Acceptable Answer

time: 22ms

memory: 4204kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #27:

score: 37

Acceptable Answer

time: 28ms

memory: 4168kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #28:

score: 37

Acceptable Answer

time: 21ms

memory: 3912kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #29:

score: 37

Acceptable Answer

time: 15ms

memory: 4172kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #30:

score: 37

Acceptable Answer

time: 24ms

memory: 3872kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #31:

score: 37

Acceptable Answer

time: 27ms

memory: 3916kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #32:

score: 37

Acceptable Answer

time: 22ms

memory: 3860kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #33:

score: 37

Acceptable Answer

time: 26ms

memory: 3912kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #34:

score: 37

Acceptable Answer

time: 23ms

memory: 3860kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #35:

score: 37

Acceptable Answer

time: 18ms

memory: 3984kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #36:

score: 37

Acceptable Answer

time: 28ms

memory: 4208kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #37:

score: 37

Acceptable Answer

time: 24ms

memory: 4204kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #38:

score: 37

Acceptable Answer

time: 30ms

memory: 3916kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #39:

score: 37

Acceptable Answer

time: 29ms

memory: 4204kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #40:

score: 37

Acceptable Answer

time: 21ms

memory: 3968kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #41:

score: 37

Acceptable Answer

time: 22ms

memory: 3912kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #42:

score: 37

Acceptable Answer

time: 24ms

memory: 4172kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #43:

score: 37

Acceptable Answer

time: 30ms

memory: 3988kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #44:

score: 37

Acceptable Answer

time: 25ms

memory: 3804kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #45:

score: 37

Acceptable Answer

time: 34ms

memory: 3912kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #46:

score: 37

Acceptable Answer

time: 13ms

memory: 3908kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #47:

score: 37

Acceptable Answer

time: 22ms

memory: 3908kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #48:

score: 37

Acceptable Answer

time: 31ms

memory: 3888kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #49:

score: 37

Acceptable Answer

time: 22ms

memory: 3860kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #50:

score: 37

Acceptable Answer

time: 30ms

memory: 4148kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #51:

score: 37

Acceptable Answer

time: 20ms

memory: 3988kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #52:

score: 37

Acceptable Answer

time: 24ms

memory: 3948kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #53:

score: 37

Acceptable Answer

time: 29ms

memory: 4172kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #54:

score: 37

Acceptable Answer

time: 22ms

memory: 3972kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #55:

score: 37

Acceptable Answer

time: 26ms

memory: 4204kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #56:

score: 37

Acceptable Answer

time: 24ms

memory: 3908kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #57:

score: 37

Acceptable Answer

time: 23ms

memory: 3920kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #58:

score: 37

Acceptable Answer

time: 23ms

memory: 3912kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #59:

score: 37

Acceptable Answer

time: 25ms

memory: 4168kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #60:

score: 37

Acceptable Answer

time: 20ms

memory: 4208kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #61:

score: 37

Acceptable Answer

time: 18ms

memory: 4176kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #62:

score: 37

Acceptable Answer

time: 24ms

memory: 3948kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)

Test #63:

score: 37

Acceptable Answer

time: 22ms

memory: 3988kb

input:

output:

result:

points 0.370 points  0.370 Accepted (partial scores)