QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#99780	#6345. Random Interactive Convex Hull Bot	tricyzhkx	AC ✓	143ms	3800kb	C++14	875b	2023-04-23 18:02:35	2023-04-23 18:02:37

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-04-23 18:02:37]
评测

测评结果：AC
用时：143ms
内存：3800kb

查看

[2023-04-23 18:02:35]
提交

answer

# include <bits/stdc++.h>
using namespace std;
int que[5010];
vector<int> conv;
bool query(int i,int j,int k)
{
	printf("? %d %d %d\n",i,j,k);fflush(stdout);
	int ans;scanf("%d",&ans);
	return ans>0;
}
int main()
{
	int n;
	cin>>n;
	if(query(1,2,3)) conv={1,2,3};
	else conv={1,3,2};
	for(int i=4;i<=n;i++)
	{
		int sz=conv.size(),l=0,r=sz-1,mid,le=0,ri=0;
		while(l<r)
		{
			mid=(l+r+1)/2;
			if(query(conv[0],conv[mid],i)) l=mid;
			else r=mid-1;
		}
		if(l && l<sz-1 && query(i,conv[l],conv[l+1])) continue;
		for(int j=l+1;j<sz;j++) que[ri++]=conv[j];
		for(int j=0;j<=l;j++) que[ri++]=conv[j];
		while(le+1<ri && query(que[ri-2],i,que[ri-1])) ri--;
		while(le+1<ri && query(que[le+1],que[le],i)) le++;
		que[ri++]=i;
		conv=vector<int>(que+le,que+ri);
	}
	cout<<"! "<<conv.size();
	for(int i:conv) cout<<" "<<i;
	return puts(""),0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3792kb

input:

5
-1
-1
-1
1
-1
1
1
-1
-1

output:

? 1 2 3
? 1 3 4
? 2 4 1
? 2 3 4
? 1 2 4
? 2 1 5
? 2 4 5
? 1 5 4
? 1 2 5
! 4 2 1 4 5

result:

ok OK, 9 queries, 4 point in hull

Test #2:

score: 0

Accepted

time: 9ms

memory: 3544kb

input:

50
-1
1
1
-1
-1
-1
1
-1
-1
-1
1
1
1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
-1
1
1
1
-1
1
1
1
-1
1
1
-1
-1
-1
-1
1
-1
-1
1
-1
1
1
-1
1
-1
-1
1
1
1
-1
1
-1
-1
-1
-1
1
-1
1
1
1
-1
1
1
1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
1
1
1
1
1
1
-1
-1
1
1
-1
-1
1
-1
1
-1
1
-1
-1
-1
1
1
1
-1
1
1
1
-...

output:

? 1 2 3
? 1 3 4
? 1 2 4
? 3 4 2
? 3 1 4
? 1 2 5
? 1 3 5
? 5 3 2
? 1 5 3
? 4 2 5
? 2 1 6
? 2 3 6
? 2 5 6
? 3 6 5
? 4 2 6
? 2 3 7
? 2 4 7
? 2 1 7
? 7 1 3
? 4 7 1
? 5 3 7
? 3 2 8
? 3 5 8
? 7 8 3
? 6 5 8
? 2 6 8
? 6 1 9
? 6 2 9
? 6 4 9
? 9 2 4
? 6 9 2
? 1 4 9
? 4 8 10
? 4 7 10
? 4 3 10
? 10 3 8
? 4 8 11...

result:

ok OK, 236 queries, 10 point in hull

Test #3:

score: 0

Accepted

time: 28ms

memory: 3728kb

input:

output:

result:

ok OK, 5133 queries, 21 point in hull

Test #4:

score: 0

Accepted

time: 49ms

memory: 3636kb

input:

2000
-1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
1
-1
-1
1
1
1
1
1
-1
1
1
1
-1
-1
-1
-1
1
-1
-1
1
-1
1
1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
1
1
1
-1
1
-1
-1
1
-1
1
1
-1
1
-1
-1
1
1
1
-1
1
1
-1
1
1
1
-1
1
1
1
1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
1
-1
1
1
1
-1
1
1
1
1
-1
-1
1
-1
-1...

output:

result:

ok OK, 10764 queries, 23 point in hull

Test #5:

score: 0

Accepted

time: 57ms

memory: 3572kb

input:

3000
1
-1
-1
-1
1
1
-1
1
-1
-1
-1
-1
1
-1
1
1
1
-1
-1
1
1
-1
-1
1
1
1
-1
-1
1
1
1
-1
-1
1
1
1
1
-1
-1
-1
1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
1
1
1
-1
1
1
-1
-1
-1
1
-1
1
1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
1
1
1
-1
-1
-1
-1
1
-1
1
1
1
1
-1
1
-...

output:

result:

ok OK, 15952 queries, 25 point in hull

Test #6:

score: 0

Accepted

time: 91ms

memory: 3608kb

input:

output:

result:

ok OK, 21800 queries, 22 point in hull

Test #7:

score: 0

Accepted

time: 121ms

memory: 3568kb

input:

4999
-1
-1
-1
-1
1
1
1
-1
-1
1
-1
-1
-1
-1
-1
1
1
1
1
-1
1
1
-1
-1
-1
1
-1
1
1
1
-1
-1
-1
-1
-1
-1
1
1
1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
-1
1
1
-1
1
1
1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
-1
1
1
-1
1
-1
-1
-1
1
-1
-1
-1
1
1
-1
1
1
1
-1
1
-1
1
-1
1
1
-1
-1
-1
1
-1
1
1
-1
1
-1
-1
-1
-1
-1...

output:

result:

ok OK, 27612 queries, 24 point in hull

Test #8:

score: 0

Accepted

time: 97ms

memory: 3788kb

input:

output:

result:

ok OK, 27293 queries, 21 point in hull

Test #9:

score: 0

Accepted

time: 135ms

memory: 3640kb

input:

5000
1
-1
-1
-1
-1
-1
-1
1
1
-1
1
-1
1
1
1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
1
-1
-1
-1
1
1
1
1
1
-1
-1
-1
1
1
1
1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
1
-1
1
-1
-1
1
1
-1
1
-1
-1
-1
-1
-1
1
1
-1
-1
1
1
1
-1
-1
1
1
1
-1
-1
-1
-1
-1
-1
1
1
1
-1
1
...

output:

result:

ok OK, 27229 queries, 27 point in hull

Test #10:

score: 0

Accepted

time: 116ms

memory: 3576kb

input:

5000
1
-1
1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
1
1
1
1
-1
1
-1
1
-1
1
-1
1
1
-1
-1
1
-1
-1
-1
1
1
1
-1
1
-1
1
1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
1
1
1
1
1
1
-1
-1
1
-1
1
1
1
-1
-1
-1
-1
-1
1
-1
1
-1
1
1
-1
-1
1
-1
1
-1
1
1
1
-1
1
1
-1
-1
-1
-1
-1
1
1
1
-1
1
1
1
-1
1
1
1
1
-1
1
1
1
-1
1
1
-1
1
-1
1
-1...

output:

result:

ok OK, 27830 queries, 25 point in hull

Test #11:

score: 0

Accepted

time: 101ms

memory: 3776kb

input:

5000
1
-1
-1
-1
1
1
1
-1
-1
1
1
-1
1
-1
-1
1
1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
1
-1
-1
1
1
-1
-1
1
1
1
-1
1
1
-1
-1
1
1
-1
-1
1
1
-1
-1
1
1
-1
1
1
-1
-1
1
-1
-1
-1
1
-1
1
-1
1
1
1
1
1
-1
-1
-1
-1
1
-1
-1
1
1
1
1
1
1
-1
-1
-1
1
1
-1
1
-1
-1
-1
1
1
1
1
-1
1
1
-1
1
1
1
1...

output:

result:

ok OK, 27092 queries, 25 point in hull

Test #12:

score: 0

Accepted

time: 108ms

memory: 3800kb

input:

5000
-1
1
-1
-1
-1
-1
1
-1
1
1
1
-1
-1
1
-1
1
1
1
1
-1
1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
1
1
-1
1
1
-1
1
1
1
-1
-1
1
-1
1
-1
-1
1
-1
-1
-1
1
-1
1
-1
1
-1
1
1
1
1
-1
-1
-1
1
-1
1
1
-1
1
1
-1
1
1
-1
1
-1
1
1
1
1
-1
1
1
-1
1
-1
1
1
1
1
-1
1
-1
1
-1
1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
-1
-1
-1
1
-1...

output:

? 1 2 3
? 1 3 4
? 1 2 4
? 4 3 2
? 1 4 3
? 1 2 4
? 2 3 5
? 2 4 5
? 5 3 4
? 2 3 6
? 2 4 6
? 3 6 4
? 1 2 6
? 2 3 7
? 2 4 7
? 7 3 4
? 2 3 8
? 2 4 8
? 2 6 8
? 4 8 6
? 1 2 8
? 3 1 8
? 1 4 9
? 1 6 9
? 9 4 6
? 1 4 10
? 1 3 10
? 8 10 1
? 4 3 10
? 3 8 11
? 3 4 11
? 10 11 3
? 6 4 11
? 4 1 12
? 4 3 12
? 4 10 12...

result:

ok OK, 27448 queries, 27 point in hull

Test #13:

score: 0

Accepted

time: 137ms

memory: 3532kb

input:

5000
1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
1
1
-1
-1
1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
1
1
1
1
1
-1
-1
1
-1
1
1
1
-1
-1
1
1
1
-1
1
-1
1
-1
1
1
-1
1
1
1
-1
-1
-1
-1
1
-1
-1
1
1
-1
-1
1
-1
1
-1
-1
1
1
-1
1
1
-1
1
1
1
-1
1
1
1
1
-1
-1
-1
-1
-1
-1
1
1
1
1
-1
-1
1
-1
1
-1
...

output:

result:

ok OK, 27694 queries, 25 point in hull

Test #14:

score: 0

Accepted

time: 113ms

memory: 3580kb

input:

5000
-1
-1
-1
-1
-1
1
1
-1
1
-1
-1
-1
1
1
1
1
-1
1
-1
1
1
-1
-1
1
1
1
1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
1
-1
1
1
1
1
-1
-1
1
1
-1
-1
-1
-1
-1
1
1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
1
1
1
1
1
1
-1
1
1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
1
-1
1
1
-1
1
-1
1
-1
-1
1
1
1
-1
-1
1
1
-1
-1
-1
-1
1
-1
-1
1...

output:

result:

ok OK, 27650 queries, 28 point in hull

Test #15:

score: 0

Accepted

time: 143ms

memory: 3552kb

input:

5000
1
1
1
1
-1
-1
1
1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
1
-1
1
1
1
-1
-1
-1
-1
1
-1
1
-1
1
-1
1
-1
1
1
-1
1
1
-1
-1
1
-1
-1
1
1
-1
-1
-1
-1
-1
1
1
1
1
-1
1
1
-1
1
1
1
1
-1
1
1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
1
1
-1
-1
1
1
-1
-1
1
1
1
-1
1
-1
-1
1
1
-1
-1
-1
1
-1
1
-1
1
1
1
-1
-1
-...

output:

result:

ok OK, 27184 queries, 23 point in hull

Test #16:

score: 0

Accepted

time: 109ms

memory: 3552kb

input:

5000
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
1
1
1
1
-1
-1
1
1
1
-1
1
-1
-1
-1
1
-1
-1
1
-1
1
-1
1
1
-1
-1
1
-1
-1
1
-1
1
-1
1
-1
1
1
1
-1
1
-1
1
1
1
-1
1
-1
1
-1
1
1
1
1
1
-1
-1
1
-1
-1
-1
1
-1
1
-1
1
-1
-1
-1
-1
1
1
1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
1
1
-1
-1
1
-1
-1
-1
1
-1
-1
1
1
1
-1
1
1
-1
1
...

output:

result:

ok OK, 27561 queries, 19 point in hull

Test #17:

score: 0

Accepted

time: 112ms

memory: 3596kb

input:

5000
1
1
1
-1
-1
1
-1
-1
-1
-1
1
1
1
1
-1
-1
-1
1
-1
-1
1
-1
1
1
1
-1
-1
1
1
-1
-1
-1
-1
-1
1
-1
1
1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
1
1
1
1
1
1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
1
-1
1
-1
-1
1
-1
-1
1
-1
-1
1
-1
1
1
1
1
1
-1
-1
-1
1
1
-1
-1
-1
-1
1
-1
1
-1
1
1
1
-1
1
-1
1
1
-1
-1
1
...

output:

result:

ok OK, 27098 queries, 25 point in hull

Test #18:

score: 0

Accepted

time: 119ms

memory: 3732kb

input:

5000
-1
1
-1
-1
-1
-1
1
1
1
-1
-1
-1
1
-1
-1
1
-1
-1
1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
1
1
1
-1
1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
1
-1
-1
-1
1
-1
-1
-1
-1
1
1
1
-1
-1
1
-1
-1
-1
1
-1
-1
1
1
-1
-1
-1
-1
1
-1
-1
1
-1
1
1
1
-1
-1
1
-1
-1
1
1
1
1
-1
1
-1
-1
-1
-1
1
-1
1
1
-1
-1
-...

output:

result:

ok OK, 27430 queries, 24 point in hull

Test #19:

score: 0

Accepted

time: 99ms

memory: 3548kb

input:

5000
-1
1
1
-1
-1
1
1
1
-1
-1
-1
-1
-1
-1
1
1
1
1
-1
1
-1
1
1
-1
-1
1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
1
-1
1
1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
1
-1
1
-1
-1
-1
1
-1
-1
1
1
1
1
-1
-1
1
1
1
1
-1
-1
1
-1
1
1
1
-1
1
1
-1
1
-1
1
1
-1
-1
-1
1
-1
1
-1
1
-1
1
1
-1
1
1
1
1...

output:

result:

ok OK, 27177 queries, 23 point in hull

Test #20:

score: 0

Accepted

time: 128ms

memory: 3632kb

input:

5000
-1
-1
-1
1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
1
1
-1
1
-1
1
-1
-1
-1
-1
1
1
1
-1
1
-1
-1
1
1
1
-1
1
1
1
1
1
1
1
-1
-1
1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
1
1
-1
1
-1
1
1
1
1
1
-1
-1
-1
-1
1
-1
1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
-1
1
1
1
1
1
-1
-1
1
-1
-1
1
1
1
1
-1
1
-1
1
1
-1
-1
-...

output:

result:

ok OK, 25095 queries, 19 point in hull

Test #21:

score: 0

Accepted

time: 82ms

memory: 3628kb

input:

5000
1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
1
1
1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
1
1
-1
-1
1
1
-1
1
1
-1
1
1
1
-1
-1
-1
-1
1
1
1
1
-1
-1
1
1
-1
1
-1
1
-1
1
1
1
-1
-1
-1
-1
-1
1
-1
1
1
-1
-1
-1
1
-1
-1
1
-1
-1
1
1
-1
1
1
1
-1
1
-1
-1
-1
-1...

output:

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

result:

ok OK, 25857 queries, 20 point in hull

Test #22:

score: 0

Accepted

time: 132ms

memory: 3548kb

input:

5000
1
1
1
-1
-1
-1
1
1
-1
1
1
-1
1
-1
-1
-1
1
1
-1
1
1
1
-1
-1
-1
-1
1
-1
-1
-1
1
-1
1
1
1
-1
-1
1
1
1
-1
-1
1
1
1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
-1
1
1
-1
1
1
-1
-1
-1
-1
1
-1
1
1
1
-1
-1
1
1
-1
-1
1
1
1
-1
-1
1
-1
-1
1
1
-1
1
1
1
1
1
1
-1
-1
-1
1
1
1
-1
1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
1
-1
1
-1
1
1...

output:

result:

ok OK, 26786 queries, 24 point in hull

Test #23:

score: 0

Accepted

time: 131ms

memory: 3560kb

input:

output:

result:

ok OK, 26732 queries, 21 point in hull