QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#32861#866. Display of SpringsFroggyguaAC ✓148ms3664kbC++171.4kb2022-05-25 09:02:142022-05-25 09:02:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-25 09:02:16]
  • 评测
  • 测评结果:AC
  • 用时:148ms
  • 内存:3664kb
  • [2022-05-25 09:02:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 100010
typedef long long ll;
int n;
int Ask(int a,int b,int k){
	if(!b)return -1;
	if(!a)return 1;
	--a,--b;
	cout<<"? "<<a<<' '<<b<<' '<<k<<endl;
	string s;
	cin>>s;
	if(s=="FIRST")return -1;
	if(s=="SECOND")return 1;
	return 0;
}
void Report(int x){
	--x;
	cout<<"! "<<x<<endl;
}
class Segment_Tree{
	int Len;
	struct node{
		int p;
	}t[N<<2];
	#define ls u<<1
	#define rs u<<1|1
	void _ins(int u,int L,int R,int id){
		if(!id)return;
		if(L==R){
			if(!t[u].p||Ask(id,t[u].p,L)==-1){
				t[u].p=id;
				return;
			}
		}
		int mid=(L+R)>>1;
		if(Ask(id,t[u].p,mid)==-1){
			swap(id,t[u].p);
		}
		if(Ask(t[u].p,id,L)==1){
			_ins(ls,L,mid,id);
		}
		else if(Ask(t[u].p,id,R)==1){
			_ins(rs,mid+1,R,id);
		}
	}
	int _query(int u,int L,int R,int pos){
		if(L==R){
			return t[u].p;
		}
		int mid=(L+R)>>1;
		int ans=t[u].p;
		int x=pos<=mid?_query(ls,L,mid,pos):_query(rs,mid+1,R,pos);
		if(Ask(ans,x,pos)==1)ans=x;
		return ans;
	}
public:
	void init(int n,int _len){
		Len=_len;
		for(int i=1;i<=n;++i){
			_ins(1,1,Len,i);
		}
	}
	int Query(int p){
		return _query(1,1,Len,p);
	}
}T;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	T.init(n,100000);
	cout<<"!"<<endl;
	while(true){
		string opt;
		cin>>opt;
		if(opt=="FINISH")break;
		int x;
		cin>>x;
		Report(T.Query(x));
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3580kb

input:

3
FIRST
FIRST
FIRST
FIRST
SECOND
QUESTION 2
SECOND
QUESTION 6
FIRST
FINISH

output:

? 1 0 50000
? 1 0 1
? 1 0 100000
? 2 1 50000
? 2 1 1
!
? 2 1 2
! 1
? 2 1 6
! 2

result:

ok Correct answer

Test #2:

score: 0
Accepted
time: 2ms
memory: 3532kb

input:

6
FIRST
EQUAL
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
QUESTION 1
SECOND
SECOND
SECOND
SECOND
QUESTION 2
EQUAL
SECOND
SECOND
SECOND
QUESTION 3
FIRST
EQUAL
SECOND
SECOND
QUESTION 4
FIRST
FIRST
EQUAL
SECOND
...

output:

? 1 0 50000
? 1 0 1
? 1 0 100000
? 2 1 50000
? 2 1 1
? 3 2 50000
? 3 2 1
? 2 1 25000
? 2 1 1
? 4 3 50000
? 4 3 1
? 3 2 25000
? 3 2 1
? 2 1 12500
? 2 1 1
? 5 4 50000
? 5 4 1
? 4 3 25000
? 4 3 1
? 3 2 12500
? 3 2 1
? 2 1 6250
? 2 1 1
!
? 2 1 1
? 3 1 1
? 4 1 1
? 5 1 1
! 1
? 2 1 2
? 3 2 2
? 4 2 2
? 5 2 ...

result:

ok Correct answer

Test #3:

score: 0
Accepted
time: 6ms
memory: 3600kb

input:

326
SECOND
FIRST
FIRST
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
SECOND
SECOND
FIRST
FIRST
SECOND
SECOND
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
SECON...

output:

? 1 0 50000
? 0 1 1
? 0 1 100000
? 2 0 50000
? 0 2 1
? 3 0 50000
? 3 0 1
? 0 2 25000
? 0 2 1
? 4 3 50000
? 3 4 1
? 4 0 25000
? 0 4 1
? 4 2 12500
? 4 2 1
? 4 2 25000
? 5 3 50000
? 3 5 1
? 3 5 100000
? 6 3 50000
? 3 6 1
? 6 0 25000
? 0 6 1
? 0 6 50000
? 7 3 50000
? 3 7 1
? 7 0 25000
? 0 7 1
? 0 7 5000...

result:

ok Correct answer

Test #4:

score: 0
Accepted
time: 18ms
memory: 3648kb

input:

19
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SEC...

output:

? 1 0 50000
? 1 0 1
? 1 0 100000
? 2 1 50000
? 1 2 1
? 1 2 100000
? 3 1 50000
? 1 3 1
? 1 3 100000
? 4 1 50000
? 1 4 1
? 1 4 100000
? 5 1 50000
? 1 5 1
? 1 5 100000
? 6 1 50000
? 6 1 1
? 7 6 50000
? 6 7 1
? 6 7 100000
? 8 6 50000
? 8 6 1
? 8 6 100000
? 9 8 50000
? 9 8 1
? 9 8 100000
? 10 9 50000
? 9...

result:

ok Correct answer

Test #5:

score: 0
Accepted
time: 21ms
memory: 3552kb

input:

500
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FI...

output:

? 1 0 50000
? 1 0 1
? 1 0 100000
? 2 1 50000
? 2 1 1
? 2 1 100000
? 3 2 50000
? 3 2 1
? 3 2 100000
? 4 3 50000
? 3 4 1
? 3 4 100000
? 5 3 50000
? 3 5 1
? 3 5 100000
? 6 3 50000
? 3 6 1
? 3 6 100000
? 7 3 50000
? 7 3 1
? 7 3 100000
? 8 7 50000
? 7 8 1
? 7 8 100000
? 9 7 50000
? 7 9 1
? 7 9 100000
? 1...

result:

ok Correct answer

Test #6:

score: 0
Accepted
time: 13ms
memory: 3612kb

input:

500
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQUAL
EQ...

output:

? 1 0 50000
? 0 1 1
? 0 1 100000
? 2 0 50000
? 0 2 1
? 0 2 100000
? 3 0 50000
? 0 3 1
? 0 3 100000
? 4 0 50000
? 0 4 1
? 0 4 100000
? 5 0 50000
? 0 5 1
? 0 5 100000
? 6 0 50000
? 0 6 1
? 0 6 100000
? 7 0 50000
? 0 7 1
? 0 7 100000
? 8 0 50000
? 0 8 1
? 0 8 100000
? 9 0 50000
? 0 9 1
? 0 9 100000
? 1...

result:

ok Correct answer

Test #7:

score: 0
Accepted
time: 36ms
memory: 3592kb

input:

500
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
F...

output:

? 1 0 50000
? 1 0 1
? 1 0 100000
? 2 1 50000
? 1 2 1
? 1 2 100000
? 3 1 50000
? 3 1 1
? 3 1 100000
? 4 3 50000
? 3 4 1
? 3 4 100000
? 5 3 50000
? 3 5 1
? 3 5 100000
? 6 3 50000
? 3 6 1
? 3 6 100000
? 7 3 50000
? 3 7 1
? 3 7 100000
? 8 3 50000
? 3 8 1
? 3 8 100000
? 9 3 50000
? 3 9 1
? 3 9 100000
? 1...

result:

ok Correct answer

Test #8:

score: 0
Accepted
time: 11ms
memory: 3544kb

input:

500
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
SECOND
FIRS...

output:

? 1 0 50000
? 0 1 1
? 0 1 100000
? 2 0 50000
? 0 2 1
? 0 2 100000
? 3 0 50000
? 0 3 1
? 0 3 100000
? 4 0 50000
? 0 4 1
? 0 4 100000
? 5 0 50000
? 0 5 1
? 0 5 100000
? 6 0 50000
? 0 6 1
? 0 6 100000
? 7 0 50000
? 0 7 1
? 0 7 100000
? 8 0 50000
? 0 8 1
? 0 8 100000
? 9 0 50000
? 0 9 1
? 0 9 100000
? 1...

result:

ok Correct answer

Test #9:

score: 0
Accepted
time: 14ms
memory: 3548kb

input:

2
FIRST
SECOND
QUESTION 64500
QUESTION 22602
FIRST
QUESTION 37446
FIRST
QUESTION 97972
QUESTION 78630
QUESTION 75591
QUESTION 63328
QUESTION 64746
QUESTION 94532
QUESTION 51275
QUESTION 12189
FIRST
QUESTION 64341
QUESTION 85825
QUESTION 63713
QUESTION 36778
FIRST
QUESTION 27116
FIRST
QUESTION 18630
...

output:

? 1 0 50000
? 1 0 1
!
! 1
? 1 0 22602
! 1
? 1 0 37446
! 1
! 1
! 1
! 1
! 1
! 1
! 1
! 1
? 1 0 12189
! 1
! 1
! 1
! 1
? 1 0 36778
! 1
? 1 0 27116
! 1
? 1 0 18630
! 1
! 1
? 1 0 28074
! 1
! 1
! 1
? 1 0 39195
! 1
! 1
? 1 0 1182
! 1
! 1
! 1
! 1
? 1 0 7017
! 1
? 1 0 13589
! 1
! 1
! 1
? 1 0 48324
! 1
! 1
! 1
...

result:

ok Correct answer

Test #10:

score: 0
Accepted
time: 19ms
memory: 3548kb

input:

2
FIRST
SECOND
QUESTION 54311
QUESTION 8466
SECOND
QUESTION 82055
QUESTION 65419
QUESTION 5271
SECOND
QUESTION 4799
SECOND
QUESTION 21521
FIRST
QUESTION 66767
QUESTION 24897
FIRST
QUESTION 69127
QUESTION 84527
QUESTION 23303
FIRST
QUESTION 88924
QUESTION 56421
QUESTION 88108
QUESTION 74033
QUESTION ...

output:

? 1 0 50000
? 1 0 1
!
! 1
? 1 0 8466
! 0
! 1
! 1
? 1 0 5271
! 0
? 1 0 4799
! 0
? 1 0 21521
! 1
! 1
? 1 0 24897
! 1
! 1
! 1
? 1 0 23303
! 1
! 1
! 1
! 1
! 1
? 1 0 25348
! 1
? 1 0 10105
! 0
! 1
? 1 0 33359
! 1
? 1 0 49782
! 1
? 1 0 20392
! 1
! 1
! 1
? 1 0 4246
! 0
! 1
? 1 0 8620
! 0
? 1 0 30435
! 1
? 1...

result:

ok Correct answer

Test #11:

score: 0
Accepted
time: 131ms
memory: 3564kb

input:

500
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
F...

output:

? 1 0 50000
? 0 1 1
? 2 0 50000
? 2 0 1
? 0 1 25000
? 0 1 1
? 3 2 50000
? 2 3 1
? 3 0 25000
? 3 0 1
? 0 1 12500
? 0 1 1
? 4 2 50000
? 4 2 1
? 2 3 25000
? 2 3 1
? 3 0 12500
? 3 0 1
? 0 1 6250
? 0 1 1
? 5 4 50000
? 4 5 1
? 5 2 25000
? 5 2 1
? 2 3 12500
? 2 3 1
? 3 0 6250
? 3 0 1
? 0 1 3125
? 0 1 1
? 6...

result:

ok Correct answer

Test #12:

score: 0
Accepted
time: 113ms
memory: 3520kb

input:

500
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
FIRST
SECOND
...

output:

? 1 0 50000
? 1 0 1
? 2 1 50000
? 2 1 1
? 1 0 25000
? 1 0 1
? 3 2 50000
? 2 3 1
? 3 1 25000
? 3 1 1
? 1 0 12500
? 1 0 1
? 4 2 50000
? 2 4 1
? 4 3 25000
? 3 4 1
? 4 1 12500
? 4 1 1
? 4 1 25000
? 5 2 50000
? 2 5 1
? 5 3 25000
? 3 5 1
? 5 4 12500
? 4 5 1
? 4 5 25000
? 5 1 18750
? 5 1 12501
? 5 1 25000
...

result:

ok Correct answer

Test #13:

score: 0
Accepted
time: 81ms
memory: 3528kb

input:

500
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
S...

output:

? 1 0 50000
? 1 0 1
? 2 1 50000
? 2 1 1
? 1 0 25000
? 1 0 1
? 3 2 50000
? 2 3 1
? 3 1 25000
? 1 3 1
? 3 0 12500
? 3 0 1
? 4 2 50000
? 2 4 1
? 4 1 25000
? 1 4 1
? 4 3 12500
? 3 4 1
? 4 0 6250
? 4 0 1
? 5 2 50000
? 2 5 1
? 5 1 25000
? 1 5 1
? 5 3 12500
? 3 5 1
? 5 4 6250
? 4 5 1
? 5 0 3125
? 0 5 1
? 6...

result:

ok Correct answer

Test #14:

score: 0
Accepted
time: 120ms
memory: 3616kb

input:

500
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECO...

output:

? 1 0 50000
? 1 0 1
? 2 1 50000
? 1 2 1
? 2 0 25000
? 2 0 1
? 3 1 50000
? 1 3 1
? 1 3 100000
? 4 1 50000
? 1 4 1
? 4 2 25000
? 2 4 1
? 4 0 12500
? 4 0 1
? 5 1 50000
? 1 5 1
? 5 2 25000
? 2 5 1
? 5 4 12500
? 4 5 1
? 4 5 25000
? 6 1 50000
? 1 6 1
? 6 2 25000
? 2 6 1
? 6 4 12500
? 4 6 1
? 4 6 25000
? 6...

result:

ok Correct answer

Test #15:

score: 0
Accepted
time: 148ms
memory: 3560kb

input:

500
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECON...

output:

? 1 0 50000
? 1 0 1
? 2 1 50000
? 2 1 1
? 1 0 25000
? 1 0 1
? 3 2 50000
? 2 3 1
? 3 1 25000
? 1 3 1
? 3 0 12500
? 3 0 1
? 4 2 50000
? 2 4 1
? 4 1 25000
? 1 4 1
? 4 3 12500
? 4 3 1
? 3 0 6250
? 3 0 1
? 5 2 50000
? 2 5 1
? 5 1 25000
? 1 5 1
? 5 4 12500
? 5 4 1
? 4 3 6250
? 4 3 1
? 3 0 3125
? 0 3 1
? 0...

result:

ok Correct answer

Test #16:

score: 0
Accepted
time: 80ms
memory: 3664kb

input:

500
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECO...

output:

? 1 0 50000
? 1 0 1
? 2 1 50000
? 1 2 1
? 2 0 25000
? 0 2 1
? 3 1 50000
? 1 3 1
? 3 0 25000
? 0 3 1
? 3 2 12500
? 3 2 1
? 4 1 50000
? 1 4 1
? 4 0 25000
? 0 4 1
? 4 3 12500
? 3 4 1
? 4 2 6250
? 4 2 1
? 5 1 50000
? 1 5 1
? 5 0 25000
? 0 5 1
? 5 3 12500
? 3 5 1
? 5 4 6250
? 5 4 1
? 5 4 12500
? 6 1 5000...

result:

ok Correct answer