QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#508344	#6345. Random Interactive Convex Hull Bot	ucup-team052	AC ✓	55ms	4068kb	C++23	2.5kb	2024-08-07 13:47:12	2024-08-07 13:47:12

Judging History

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

[2024-08-07 13:47:12]
评测

测评结果：AC
用时：55ms
内存：4068kb

查看

[2024-08-07 13:47:12]
提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
using namespace std;
using LL=long long;
#define N 5005
int x[N],y[N];
int ccw(int i,int j,int k)
{
	printf("? %d %d %d\n",i,j,k);
#ifdef xay5421
	int tw=(x[j]-x[i])*(y[k]-y[i])-(y[j]-y[i])*(x[k]-x[i]);
	printf("A %d\n",tw>0?1:-1);
	return tw>0;
#endif
	fflush(stdout);
	int ret;
	scanf("%d",&ret);
	return ret==1;
}
int main(){
	int n;
#ifdef xay5421
	freopen("a.in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
#else
	cin>>n;
#endif
	vector<int> ans;
	if(ccw(1,2,3)) ans={1,3,2};
	else ans={1,2,3};
	for(int i=4;i<=n;i++)
	{
		int l=1,r=(int)ans.size()-1,pos=-1;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(ccw(ans[0],ans[mid],i)) pos=mid,r=mid-1;
			else l=mid+1;
		}
		// printf("* %d\n",pos);
		if(pos>1)
		{
			if(ccw(ans[pos],ans[pos-1],i)) {}
			else
			{
				vector<int> nw;
				for(int j=0;j<pos;j++) nw.push_back(ans[j]);
				while(nw.size()>=2)
				{
					if(ccw(nw[(int)nw.size()-1],nw[(int)nw.size()-2],i)) break;
					else nw.pop_back();
				}
				int tpos=pos;
				while(tpos+1<(int)ans.size())
				{
					if(ccw(ans[tpos],ans[tpos+1],i)==0) break;
					else tpos++;
				}
				nw.push_back(i);
				for(int j=tpos;j<(int)ans.size();j++) nw.push_back(ans[j]);
				ans=nw;
			}
		}
		else if(pos==1)
		{
			vector<int> nw;
			nw.push_back(i);
			int tpos=1;
			while(tpos+1<(int)ans.size())
			{
				if(ccw(ans[tpos],ans[tpos+1],i)==0) break;
				else tpos++;
			}
			for(int i=tpos;i<(int)ans.size();i++) nw.push_back(ans[i]);
			nw.push_back(ans[0]);
			while(nw.size()>=3)
			{
				if(ccw(nw[(int)nw.size()-1],nw[(int)nw.size()-2],i)) break;
				else nw.pop_back();
			}
			ans=nw;
		}
		else
		{
			vector<int> nw;
			nw.push_back(i);
			int tpos=0;
			while(tpos+1<(int)ans.size())
			{
				if(ccw(ans[tpos],ans[tpos+1],i)==0) break;
				else tpos++;
			}
			for(int i=tpos;i<(int)ans.size();i++) nw.push_back(ans[i]);
			while(nw.size()>=3)
			{
				if(ccw(nw[(int)nw.size()-1],nw[(int)nw.size()-2],i)) break;
				else nw.pop_back();
			}
			ans=nw;
		}
		// printf("ans[%d] = ",i);
		// for(int i=0;i<(int)ans.size();i++) printf("%d%c",ans[i]," \n"[i==(int)ans.size()-1]);
	}
	printf("! %d ",(int)ans.size());
	reverse(ans.begin(),ans.end());
	for(int i=0;i<(int)ans.size();i++) printf("%d%c",ans[i]," \n"[i==(int)ans.size()-1]);
	return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 4020kb

input:

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

output:

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

result:

ok OK, 10 queries, 4 point in hull

Test #2:

score: 0

Accepted

time: 0ms

memory: 3772kb

input:

output:

result:

ok OK, 228 queries, 10 point in hull

Test #3:

score: 0

Accepted

time: 12ms

memory: 3768kb

input:

output:

result:

ok OK, 5060 queries, 21 point in hull

Test #4:

score: 0

Accepted

time: 10ms

memory: 3776kb

input:

output:

result:

ok OK, 10813 queries, 23 point in hull

Test #5:

score: 0

Accepted

time: 0ms

memory: 4056kb

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
1
...

output:

result:

ok OK, 15636 queries, 25 point in hull

Test #6:

score: 0

Accepted

time: 18ms

memory: 3800kb

input:

output:

result:

ok OK, 21661 queries, 22 point in hull

Test #7:

score: 0

Accepted

time: 26ms

memory: 4068kb

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
-1
-1
1
1
-...

output:

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

result:

ok OK, 27806 queries, 24 point in hull

Test #8:

score: 0

Accepted

time: 29ms

memory: 3792kb

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, 27017 queries, 21 point in hull

Test #9:

score: 0

Accepted

time: 29ms

memory: 4060kb

input:

output:

result:

ok OK, 27494 queries, 27 point in hull

Test #10:

score: 0

Accepted

time: 33ms

memory: 3772kb

input:

output:

result:

ok OK, 27869 queries, 25 point in hull

Test #11:

score: 0

Accepted

time: 55ms

memory: 4056kb

input:

output:

result:

ok OK, 27318 queries, 25 point in hull

Test #12:

score: 0

Accepted

time: 17ms

memory: 3856kb

input:

output:

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

result:

ok OK, 27259 queries, 27 point in hull

Test #13:

score: 0

Accepted

time: 38ms

memory: 3864kb

input:

output:

result:

ok OK, 27824 queries, 25 point in hull

Test #14:

score: 0

Accepted

time: 30ms

memory: 4064kb

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, 27870 queries, 28 point in hull

Test #15:

score: 0

Accepted

time: 26ms

memory: 4024kb

input:

output:

result:

ok OK, 26673 queries, 23 point in hull

Test #16:

score: 0

Accepted

time: 24ms

memory: 3864kb

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 2 4
? 1 3 4
? 3 2 4
? 2 1 4
? 1 4 5
? 1 3 5
? 1 2 5
? 3 4 5
? 5 2 6
? 5 4 6
? 4 2 6
? 2 1 6
? 4 3 6
? 5 6 7
? 5 4 7
? 4 6 7
? 6 2 7
? 2 1 7
? 4 3 7
? 5 7 8
? 5 1 8
? 5 2 8
? 2 1 8
? 1 5 8
? 2 7 8
? 7 4 8
? 5 7 9
? 5 1 9
? 1 8 9
? 8 7 9
? 5 3 9
? 9 4 10
? 9 8 10
? 9 7 10
? 7 8 10
? 9 4 11...

result:

ok OK, 27325 queries, 19 point in hull

Test #17:

score: 0

Accepted

time: 37ms

memory: 3768kb

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, 26971 queries, 25 point in hull

Test #18:

score: 0

Accepted

time: 44ms

memory: 3796kb

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, 27443 queries, 24 point in hull

Test #19:

score: 0

Accepted

time: 5ms

memory: 3820kb

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, 26632 queries, 23 point in hull

Test #20:

score: 0

Accepted

time: 16ms

memory: 3764kb

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, 25093 queries, 19 point in hull

Test #21:

score: 0

Accepted

time: 46ms

memory: 3768kb

input:

output:

result:

ok OK, 25832 queries, 20 point in hull

Test #22:

score: 0

Accepted

time: 10ms

memory: 3768kb

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, 26957 queries, 24 point in hull

Test #23:

score: 0

Accepted

time: 24ms

memory: 3724kb

input:

output:

result:

ok OK, 26297 queries, 21 point in hull