QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#744822 | #9484. Colored Complete Graph | P-Bao | WA | 1ms | 3820kb | C++23 | 1.6kb | 2024-11-13 23:39:39 | 2024-11-13 23:39:40 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
char query(int x, int y){
cout << "? " << x + 1 << " " << y + 1 << endl;
//cout.flush();
char res;
cin >> res;
return res;
}
void answer(vector<vector<int> > res){
cout << "!" << endl;
for(int i = 0; i < res.size(); i++)
cout << res[i][0] + 1 << " " << res[i][1] + 1 << endl;
}
int n;
vector<vector< vector<int> > > adj(2);
vector<vector<int> > target(2); // target[0]: 0->i có màu R ; target[1]: 0->i có màu B
pair<int, int> pos = {1, 1};
void Krusal(){
while(max(adj[0].size(), adj[1].size()) < n - 1){
int u = target[0][pos.first], v = target[1][pos.second];
char res = query(u, v);
if(res == 'R'){
adj[0].push_back({u, v});
pos.first++;
}
else{
adj[1].push_back({u, v});
pos.second++;
}
}
if(adj[0].size() == n - 1) answer(adj[0]);
else answer(adj[1]);
}
void solve(){
cin >> n;
target[0].emplace_back(0);
target[1].emplace_back(0);
for(int i = 1; i < n; i++){
char res = query(0, i);
if(res == 'R'){
target[0].emplace_back(i);
adj[0].push_back({0, i});
}
else{
target[1].emplace_back(i);
adj[1].push_back({0, i});
}
}
Krusal();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3820kb
input:
3 B R B
output:
? 1 2 ? 1 3 ? 3 2 ! 1 2 3 2
result:
ok AC
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3716kb
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 ...
result:
wrong answer guessed graph is incorrect