QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #674557 | #9484. Colored Complete Graph | The_clear_pool | TL | 1ms | 3732kb | C++14 | 3.0kb | 2024-10-25 16:28:43 | 2024-10-25 16:28:43 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 100100
int n;
int vis[N];//1为red，2为blue
int cnt[3];
inline int op(int x){
if(x==1) return 2;
return 1;
}
#define pii pair<int,int>
#define mp make_pair
pii ans[N][3];
int main(){
scanf("%d",&n);
// if(n==3){
// printf("? 1 2\n");
// fflush(stdout);
// char ch=getchar();
// while(ch!='R'&&ch!='B') ch=getchar();
// printf("? 1 3\n");
// fflush(stdout);
// printf("? 3 2\n");
// fflush(stdout);
// cout<<"!\n";
// cout<<"1 2\n";
// cout<<"3 2\n";
// return 0;
// }
for(int i=2;i<=n;i++){
char ch;
printf("? %d %d\n",1,i);//n-1次询问
fflush(stdout);
ch=getchar();
while(ch!='R'&&ch!='B') ch=getchar();
if(ch=='R'){
vis[i]=1;
cnt[1]++;
ans[cnt[1]][1]=mp(1,i);
}
else{
vis[i]=2;
cnt[2]++;
ans[cnt[2]][2]=mp(1,i);
}
}
if(cnt[1]==n-1||cnt[2]==n-1){
printf("!\n");
for(int i=2;i<=n;i++){
printf("%d %d\n",1,i);
}
}
else{
int tmp=0;
if(cnt[1]>cnt[2]){
tmp=1;
}
else{
tmp=2;
}
for(int i=2;i<=n;i++){
if(vis[i]==tmp){
for(int j=2;j<=n;j++){
if(j!=i&&vis[j]!=tmp){
char ch;
int color;
printf("? %d %d\n",j,i);//(n-2)次询问
fflush(stdout);
ch=getchar();
while(ch!='B'&&ch!='R'){
ch=getchar();
if(ch=='F'){
return 0;
}
}
if(ch=='R') color=1;
else color=2;
if(color==op(tmp)){
cnt[op(tmp)]++;
ans[cnt[op(tmp)]][op(tmp)]=mp(i,j);
break;
}
else{
cnt[tmp]++;
vis[j]=tmp;
ans[cnt[tmp]][tmp]=mp(i,j);
if(cnt[tmp]==n-1){
printf("!\n");
for(int k=1;k<=n-1;k++){
printf("%d %d\n",ans[k][tmp].first,ans[k][tmp].second);
}
return 0;
}
}
}
}
}
}
printf("!\n");
for(int i=1;i<=n-1;i++){
printf("%d %d\n",ans[i][op(tmp)].first,ans[i][op(tmp)].second);
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3732kb
input:
3 B R B
output:
? 1 2 ? 1 3 ? 3 2 ! 1 2 2 3
result:
ok AC
Test #2:
score: -100
Time Limit Exceeded
input:
983 B R R B B B B B R B R R R R R R R B B R R B R B R R B B R B R R R R B R B B B R R R B B R R B R B R B B B R B R R B R B B R R R B B B B R B R R B R B B R B R B R B R R R B B B R R B B B R R B R B B B R B B R R B B R R R R B R R B B B R B B B B R B R R B R R R B R R B R R B R R B R B R B B R B R ...
output:
? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 1 6 ? 1 7 ? 1 8 ? 1 9 ? 1 10 ? 1 11 ? 1 12 ? 1 13 ? 1 14 ? 1 15 ? 1 16 ? 1 17 ? 1 18 ? 1 19 ? 1 20 ? 1 21 ? 1 22 ? 1 23 ? 1 24 ? 1 25 ? 1 26 ? 1 27 ? 1 28 ? 1 29 ? 1 30 ? 1 31 ? 1 32 ? 1 33 ? 1 34 ? 1 35 ? 1 36 ? 1 37 ? 1 38 ? 1 39 ? 1 40 ? 1 41 ? 1 42 ? 1 43 ? 1 44 ? 1 45 ...