QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#744822#9484. Colored Complete GraphP-BaoWA 1ms3820kbC++231.6kb2024-11-13 23:39:392024-11-13 23:39:40

Judging History

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

  • [2024-11-13 23:39:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3820kb
  • [2024-11-13 23:39:39]
  • 提交

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