QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#535860	#6345. Random Interactive Convex Hull Bot	fzx	AC ✓	71ms	3808kb	C++14	1.2kb	2024-08-28 15:52:27	2024-08-28 15:52:28

Judging History

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

[2024-08-28 15:52:28]
评测

测评结果：AC
用时：71ms
内存：3808kb

查看

[2024-08-28 15:52:27]
提交

answer

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int INF=1e6+5;
int vis5[INF],n;
int query(int x,int y,int z) {
	cout<<"? "<<x<<" "<<y<<" "<<z<<endl;
	int xx=0;cin>>xx;
	if (xx==1) xx=-1;
	else xx=1;
	return xx;
}
signed main()
{	
	cin>>n;
	vector <int> v;
	if (query(1,2,3)==-1) {v.pb(1);v.pb(2);v.pb(3);}
	else {v.pb(1);v.pb(3);v.pb(2);}
	for (int i=4;i<=n;i++) {
		int len=v.size();
		for (int j=0;j<len;j++) vis5[j]=0;
		int l=1,r=len-1,ans=len;
		while (l<=r) {
			int Mid=(l+r)>>1;
			if (query(v[0],v[Mid],i)==1) r=(ans=Mid)-1;
			else l=Mid+1;
		}
		ans--;
		int id=ans;
		if (query(v[id],v[(id+1)%len],i)==-1) continue;
		vis5[id]++;vis5[(id+1)%len]++;
		int L=id,R=(id+1)%len;
		while (query(v[(L+len-1)%len],v[L],i)==1) L+=len-1,L%=len,vis5[L]++,vis5[(L+1)%len]++;
		while (query(v[R],v[(R+1)%len],i)==1) vis5[R]++,vis5[(R+1)%len]++,R++,R%=len;
		vector <int> v3;
		int fl=1;
		for (int j=0;j<len;j++) {
			if (vis5[j]<=1) v3.pb(v[j]);
			if (vis5[j] && vis5[(j+1)%len]) {if (fl) v3.pb(i);fl=0;}
		}
		v=v3;
		// cout<<v.size()<<" ";
		// for (int i:v) cout<<i<<" ";
		// cout<<"\n";
	}
	cout<<"! ";
	cout<<v.size()<<" ";
	for (int i:v) cout<<i<<" ";
	cout<<"\n";
	cout<<endl;
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3772kb

input:

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

output:

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

result:

ok OK, 11 queries, 4 point in hull

Test #2:

score: 0

Accepted

time: 1ms

memory: 3600kb

input:

output:

result:

ok OK, 238 queries, 10 point in hull

Test #3:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

output:

result:

ok OK, 5170 queries, 21 point in hull

Test #4:

score: 0

Accepted

time: 30ms

memory: 3604kb

input:

output:

result:

ok OK, 10903 queries, 23 point in hull

Test #5:

score: 0

Accepted

time: 5ms

memory: 3516kb

input:

output:

result:

ok OK, 16013 queries, 25 point in hull

Test #6:

score: 0

Accepted

time: 45ms

memory: 3540kb

input:

output:

result:

ok OK, 22050 queries, 22 point in hull

Test #7:

score: 0

Accepted

time: 43ms

memory: 3504kb

input:

output:

result:

ok OK, 27371 queries, 24 point in hull

Test #8:

score: 0

Accepted

time: 35ms

memory: 3588kb

input:

output:

result:

ok OK, 26422 queries, 21 point in hull

Test #9:

score: 0

Accepted

time: 22ms

memory: 3804kb

input:

output:

result:

ok OK, 27828 queries, 27 point in hull

Test #10:

score: 0

Accepted

time: 21ms

memory: 3740kb

input:

output:

result:

ok OK, 28099 queries, 25 point in hull

Test #11:

score: 0

Accepted

time: 37ms

memory: 3584kb

input:

output:

result:

ok OK, 27227 queries, 25 point in hull

Test #12:

score: 0

Accepted

time: 38ms

memory: 3596kb

input:

output:

result:

ok OK, 27533 queries, 27 point in hull

Test #13:

score: 0

Accepted

time: 25ms

memory: 3516kb

input:

output:

result:

ok OK, 27839 queries, 25 point in hull

Test #14:

score: 0

Accepted

time: 64ms

memory: 3772kb

input:

output:

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

result:

ok OK, 28222 queries, 28 point in hull

Test #15:

score: 0

Accepted

time: 29ms

memory: 3476kb

input:

output:

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

result:

ok OK, 26660 queries, 23 point in hull

Test #16:

score: 0

Accepted

time: 44ms

memory: 3512kb

input:

output:

result:

ok OK, 27802 queries, 19 point in hull

Test #17:

score: 0

Accepted

time: 38ms

memory: 3584kb

input:

output:

result:

ok OK, 27546 queries, 25 point in hull

Test #18:

score: 0

Accepted

time: 58ms

memory: 3524kb

input:

output:

result:

ok OK, 27313 queries, 24 point in hull

Test #19:

score: 0

Accepted

time: 44ms

memory: 3548kb

input:

output:

result:

ok OK, 27602 queries, 23 point in hull

Test #20:

score: 0

Accepted

time: 71ms

memory: 3808kb

input:

output:

result:

ok OK, 25014 queries, 19 point in hull

Test #21:

score: 0

Accepted

time: 42ms

memory: 3464kb

input:

output:

result:

ok OK, 25616 queries, 20 point in hull

Test #22:

score: 0

Accepted

time: 47ms

memory: 3744kb

input:

output:

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

result:

ok OK, 27078 queries, 24 point in hull

Test #23:

score: 0

Accepted

time: 34ms

memory: 3476kb

input:

output:

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

result:

ok OK, 26109 queries, 21 point in hull