QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#143085#6668. Trokutitatyam#0 15ms3848kbC++173.2kb2023-08-20 15:48:522024-07-04 01:50:34

Judging History

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

  • [2024-07-04 01:50:34]
  • 评测
  • 测评结果:0
  • 用时:15ms
  • 内存:3848kb
  • [2023-08-20 15:48:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
bool chmin(ll& a, ll b) { if(a <= b) return 0; a = b; return 1; }

/*
 1 辺 / query では足りず, 1.5 辺 / query でないといけない
 0 か 3 が帰ってきた → 3 辺確定
 1 が帰ってきた → 4 頂点で聞いてみる?
 6 辺 4 クエリなので, 足りないかな
 5 頂点: 10 辺 10 クエリ 線形独立か? そうっぽい
 すでにわかっているクリークと 1 頂点で比較する.
 0 か 2 が出れば 2 辺確定, 1 が出たら 0 か 2 が出るまで新しいのと交差させ, それでもだめならすでにわかっている辺を入れる
 乱択で期待値 1.5 辺 / query か?
 */
int query(int a, int b, int c) {
    cout << "? " << a + 1 << " " << b + 1 << " " << c + 1 << endl;
    int x;
    cin >> x;
    return x;
}
int main() {
    mt19937 rnd;
    const int N = 100;
    vector g(N, vector(N, false));
    int q[5][5][5] = {};
    int sum = 0;
    for(int a = 0; a < 5; a++) for(int b = a + 1; b < 5; b++) for(int c = b + 1; c < 5; c++) {
        sum += q[a][b][c] = q[a][c][b] = q[b][a][c] = q[b][c][a] = q[c][a][b] = q[c][b][a] = query(a, b, c);
    }
    sum /= 3;
    for(int a = 0; a < 5; a++) for(int b = a + 1; b < 5; b++) {
        vector<int> other = {0, 1, 2, 3, 4};
        other.erase(other.begin() + b);
        other.erase(other.begin() + a);
        const int c = other[0], d = other[1], e = other[2];
        int x = sum * 2;
        x -= q[c][d][a];
        x -= q[c][d][b];
        x -= q[a][c][e];
        x -= q[a][d][e];
        x -= q[b][d][e];
        x -= q[b][c][e];
        g[a][b] = g[b][a] = x;
    }
    for(int i = 5; i < N; i++) {
        auto Q = [&](int a, int b) {
            return query(a, b, i) - g[a][b];
        };
        auto set = [&](int a, bool x) {
            g[a][i] = g[i][a] = x;
        };
        vector<int> c(i);
        iota(c.begin(), c.end(), 0);
        shuffle(c.begin(), c.end(), rnd);
        for(int l = 0; l < c.size(); l++) [&]{
            if(l == c.size() - 1) {
                set(c[l], Q(0, c[l]) - g[i][0]);
                return;
            }
            int r = l + 1;
            while(r < c.size()) {
                r++;
                const int q = Q(c[r - 2], c[r - 1]);
                if(q != 1) {
                    set(c[--r], q);
                    set(c[--r], q);
                    while(l < r) {
                        r--;
                        set(c[r], !g[i][c[r + 1]]);
                    }
                    return;
                }
            }
            if(l) {
                set(c[l], Q(0, c[l]) - g[i][0]);
                for(; l + 1 < c.size(); l++) {
                    set(c[l + 1], !g[i][c[l]]);
                }
                return;
            }
            const int q = Q(c[0], c[2]);
            assert(q != 1);
            set(c[0], q);
            for(; l + 1 < c.size(); l++) {
                set(c[l + 1], !g[i][c[l]]);
            }
        }();
    }
    cout << "!\n";
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) cout << g[i][j];
        cout << endl;
    }
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 30
Acceptable Answer
time: 6ms
memory: 3848kb

input:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

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

result:

points 0.30 points  0.30 correct 4950 queries

Test #2:

score: 30
Acceptable Answer
time: 0ms
memory: 3620kb

input:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

output:

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

result:

points 0.30 points  0.30 correct 4950 queries

Test #3:

score: 29.9939
Acceptable Answer
time: 3ms
memory: 3600kb

input:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

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

result:

points 0.29993939390 points  0.29993939390 correct 4953 queries

Test #4:

score: 29.9939
Acceptable Answer
time: 9ms
memory: 3620kb

input:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

output:

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

result:

points 0.29993939390 points  0.29993939390 correct 4953 queries

Test #5:

score: 29.9455
Acceptable Answer
time: 6ms
memory: 3608kb

input:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

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

result:

points 0.29945454550 points  0.29945454550 correct 4977 queries

Test #6:

score: 29.9434
Acceptable Answer
time: 0ms
memory: 3656kb

input:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

output:

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

result:

points 0.29943434340 points  0.29943434340 correct 4978 queries

Test #7:

score: 0
Wrong Answer
time: 15ms
memory: 3568kb

input:

0
0
1
0
1
1
0
0
0
0
1
1
1
1
1
1
0
0
1
0
0
0
1
1
1
1
0
0
2
1
1
1
2
2
2
1
0
0
1
0
0
0
0
2
1
0
0
0
0
0
1
2
0
1
2
2
1
0
0
1
0
0
0
0
0
0
0
1
1
2
2
2
2
3
1
2
2
2
2
3
2
2
2
2
3
2
2
2
3
2
2
3
2
3
3
2
1
2
1
2
2
0
2
0
0
0
1
0
0
0
0
1
0
1
2
1
1
0
1
0
0
1
0
1
0
1
0
1
2
2
2
0
0
1
1
1
1
1
1
1
1
0
1
2
1
1
0
1
1
0
...

output:

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

result:

wrong answer the graph you report is incorrect