QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#535537	#6345. Random Interactive Convex Hull Bot	World_Creater	TL	44ms	3704kb	C++14	1.2kb	2024-08-28 09:30:22	2024-08-28 09:30:22

Judging History

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

[2024-08-28 09:30:22]
评测

测评结果：TL
用时：44ms
内存：3704kb

查看

[2024-08-28 09:30:22]
提交

answer

#include<bits/stdc++.h>
using namespace std;
vector<int>an,ans;
int vs[5005];
int query(int a,int b,int c)
{
    cout<<"? "<<a<<" "<<b<<" "<<c<<endl;
    int t;
    cin>>t;
    return t;
}
void sol(int x){
	for(int i=0;i<an.size();++i)vs[i]=0;int si=an.size();int o=(x+1)%si;
	while(query(an[x],an[o],an[(o+1)%si])<0)vs[o]=1,o=(o+1)%si;
	o=(x-1+si)%si;
	while(query(an[x],an[o],an[(o+si-1)%si])>0)vs[o]=1,o=(o+si-1)%si;
	ans.clear();
	for(int i=0;i<si;++i)if(!vs[i])ans.push_back(an[i]);
	an=ans;
}
int main()
{
    int n;
    cin>>n;
	an.clear();
	if(query(1,2,3)<0)an.push_back(1),an.push_back(3),an.push_back(2);
	else an.push_back(1),an.push_back(2),an.push_back(3);
	for(int i=4;i<=n;++i){
		if(query(an[0],an[1],i)<0)an.insert(an.begin()+1,i),sol(1);
		else{
			int l=2,r=an.size();
			while(l<r){
				int md=l+r>>1;
				if(query(an[0],an[md],i)<0)r=md;else l=md+1;
			}
			if(l==an.size()){
				an.push_back(i),sol(an.size()-1);
			}else if(query(an[l-1],an[l],i)<0){
				an.insert(an.begin()+l,i),sol(l);
			}
		}
	}
    cout<<"! "<<an.size()<<" ";
    for(auto i:an)
    {
        cout<<i<<" ";
    }
    cout<<endl;
}//query(a,b,c):c on ab right:-1

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3664kb

input:

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

output:

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

result:

ok OK, 10 queries, 4 point in hull

Test #2:

score: 0

Accepted

time: 4ms

memory: 3644kb

input:

output:

result:

ok OK, 257 queries, 10 point in hull

Test #3:

score: 0

Accepted

time: 4ms

memory: 3704kb

input:

output:

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

result:

ok OK, 6068 queries, 21 point in hull

Test #4:

score: 0

Accepted

time: 7ms

memory: 3584kb

input:

output:

result:

ok OK, 12408 queries, 23 point in hull

Test #5:

score: 0

Accepted

time: 19ms

memory: 3656kb

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

output:

result:

ok OK, 18455 queries, 25 point in hull

Test #6:

score: 0

Accepted

time: 44ms

memory: 3644kb

input:

output:

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

result:

ok OK, 24537 queries, 22 point in hull

Test #7:

score: -100

Time Limit Exceeded

input:

output: