QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #674536 | #9484. Colored Complete Graph | The_clear_pool | TL | 0ms | 3796kb | C++14 | 2.7kb | 2024-10-25 16:21:21 | 2024-10-25 16:21:21 |
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);
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");
fflush(stdout);
for(int i=2;i<=n;i++){
printf("%d %d\n",1,i);
fflush(stdout);
}
}
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=='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");
fflush(stdout);
for(int k=1;k<=n-1;k++){
printf("%d %d\n",ans[k][tmp].first,ans[k][tmp].second);
fflush(stdout);
}
return 0;
}
}
}
}
}
}
printf("!\n");
fflush(stdout);
for(int i=1;i<=n-1;i++){
printf("%d %d\n",ans[i][op(tmp)].first,ans[i][op(tmp)].second);
fflush(stdout);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3796kb
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 ...