QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#143085 | #6668. Trokuti | tatyam# | 0 | 15ms | 3848kb | C++17 | 3.2kb | 2023-08-20 15:48:52 | 2024-07-04 01:50:34 |
Judging History
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;
}
}
Details
Tip: Click on the bar to expand more detailed information
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