QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#488741	#6345. Random Interactive Convex Hull Bot	World_Creater	AC ✓	64ms	3824kb	C++14	933b	2024-07-24 15:04:10	2024-07-24 15:04:10

Judging History

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

[2024-07-24 15:04:10]
评测

测评结果：AC
用时：64ms
内存：3824kb

查看

[2024-07-24 15:04:10]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int n;
deque<int> vec;
int query(int x,int y,int z)
{
	cout<<"? "<<x<<" "<<y<<" "<<z<<endl;
	int f;
	cin>>f;
	return f;
}
int main()
{
	cin>>n;
	if(query(1,2,3)==1)
	{
		vec.emplace_back(1);
		vec.emplace_back(2);
		vec.emplace_back(3);
	}
	else
	{
		vec.emplace_back(1);
		vec.emplace_back(3);
		vec.emplace_back(2);
	}
	for(int i=4;i<=n;i++)
	{
		int l=0,r=vec.size()-1;
		while(l<r)
		{
			int mid=(l+r+1)>>1;
			if(query(vec[0],vec[mid],i)==1) l=mid;
			else r=mid-1;
		}
		if(l>0&&l<vec.size()-1&&query(vec[l],vec[l+1],i)==1) continue ;
		bool fl=0;
		rotate(vec.begin(),vec.begin()+l+1,vec.end());
		while(query(vec[0],vec[1],i)==-1) vec.pop_front(),fl=1;
		while(query(vec[vec.size()-2],vec[vec.size()-1],i)==-1) vec.pop_back(),fl=1;
		vec.emplace_front(i);
	}
	cout<<"! "<<vec.size()<<" ";
	for(auto i:vec) cout<<i<<" ";
	cout<<endl;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3820kb

input:

output:

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

result:

ok OK, 8 queries, 4 point in hull

Test #2:

score: 0

Accepted

time: 0ms

memory: 3476kb

input:

output:

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

result:

ok OK, 234 queries, 10 point in hull

Test #3:

score: 0

Accepted

time: 18ms

memory: 3520kb

input:

output:

result:

ok OK, 5144 queries, 21 point in hull

Test #4:

score: 0

Accepted

time: 9ms

memory: 3592kb

input:

output:

result:

ok OK, 10872 queries, 23 point in hull

Test #5:

score: 0

Accepted

time: 8ms

memory: 3824kb

input:

output:

result:

ok OK, 15868 queries, 25 point in hull

Test #6:

score: 0

Accepted

time: 23ms

memory: 3584kb

input:

output:

result:

ok OK, 21307 queries, 22 point in hull

Test #7:

score: 0

Accepted

time: 64ms

memory: 3600kb

input:

output:

result:

ok OK, 27477 queries, 24 point in hull

Test #8:

score: 0

Accepted

time: 57ms

memory: 3780kb

input:

output:

result:

ok OK, 27049 queries, 21 point in hull

Test #9:

score: 0

Accepted

time: 48ms

memory: 3608kb

input:

output:

result:

ok OK, 27447 queries, 27 point in hull

Test #10:

score: 0

Accepted

time: 27ms

memory: 3472kb

input:

output:

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

result:

ok OK, 28061 queries, 25 point in hull

Test #11:

score: 0

Accepted

time: 56ms

memory: 3584kb

input:

output:

result:

ok OK, 27057 queries, 25 point in hull

Test #12:

score: 0

Accepted

time: 20ms

memory: 3596kb

input:

output:

result:

ok OK, 27233 queries, 27 point in hull

Test #13:

score: 0

Accepted

time: 51ms

memory: 3592kb

input:

output:

result:

ok OK, 28306 queries, 25 point in hull

Test #14:

score: 0

Accepted

time: 21ms

memory: 3776kb

input:

output:

result:

ok OK, 27699 queries, 28 point in hull

Test #15:

score: 0

Accepted

time: 37ms

memory: 3520kb

input:

output:

result:

ok OK, 26567 queries, 23 point in hull

Test #16:

score: 0

Accepted

time: 33ms

memory: 3476kb

input:

output:

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

result:

ok OK, 27290 queries, 19 point in hull

Test #17:

score: 0

Accepted

time: 57ms

memory: 3548kb

input:

output:

result:

ok OK, 27252 queries, 25 point in hull

Test #18:

score: 0

Accepted

time: 58ms

memory: 3776kb

input:

output:

result:

ok OK, 27362 queries, 24 point in hull

Test #19:

score: 0

Accepted

time: 24ms

memory: 3776kb

input:

output:

result:

ok OK, 26960 queries, 23 point in hull

Test #20:

score: 0

Accepted

time: 30ms

memory: 3588kb

input:

output:

result:

ok OK, 25162 queries, 19 point in hull

Test #21:

score: 0

Accepted

time: 52ms

memory: 3608kb

input:

output:

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

result:

ok OK, 25847 queries, 20 point in hull

Test #22:

score: 0

Accepted

time: 42ms

memory: 3780kb

input:

output:

result:

ok OK, 26964 queries, 24 point in hull

Test #23:

score: 0

Accepted

time: 49ms

memory: 3540kb

input:

output:

result:

ok OK, 26905 queries, 21 point in hull