QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116933 | #6668. Trokuti | Linshey# | 0 | 6ms | 4100kb | C++14 | 4.7kb | 2023-06-30 10:56:57 | 2024-05-31 18:35:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std; const int maxn = 1e2 + 5, n = 100;
mt19937 rnd(2333);
int mp[maxn][maxn];
// #define _DEBUG_
inline int ask(int a, int b, int c)
{
assert(a != b && b != c && c != a);
#ifdef _DEBUG_
return mp[a][b] + mp[b][c] + mp[c][a];
#else
printf("? %d %d %d\n", a, b, c), fflush(stdout);
int x; scanf("%d", &x); return x;
#endif
}
int Mp[maxn][maxn];
namespace Solve5
{
const int maxm = 12;
double A[maxm][maxm], ans[maxm]; pair<int, int> eg[maxm]; int m, M = 0;
inline int id(int i, int j) { for (int k = 1; k <= 10; k++) if (eg[k] == make_pair(i, j)) return k; assert(0); }
inline void solve()
{
for (int i = 1; i <= 5; i++) for (int j = i + 1; j <= 5; j++) eg[++m] = { i, j };
assert(m == 10);
for (int a = 1; a <= 5; a++) for (int b = a + 1; b <= 5; b++) for (int c = b + 1; c <= 5; c++)
{
++M;
A[M][id(a, b)] = A[M][id(a, c)] = A[M][id(b, c)] = 1, A[M][m + 1] = ask(a, b, c);
}
assert(M == 10);
for (int j = 1; j <= m; j++)
{
for (int i = j; i <= m; i++) if (fabs(A[i][j]) > 1e-9) { swap(A[i], A[j]), swap(eg[i], eg[j]); break; }
if (fabs(A[j][j]) <= 1e-9) { cerr << "5 is too small!" << endl; return; }
double iv = 1 / A[j][j];
for (int k = j; k <= m + 1; k++) A[j][k] *= iv;
for (int i = j + 1; i <= m; i++)
{
double v = A[i][j];
for (int k = j + 1; k <= m + 1; k++) A[i][k] -= v * A[j][k];
}
}
for (int j = m; j; j--)
{
ans[j] = A[j][m + 1];
for (int i = j - 1; i; i--) A[i][m + 1] -= A[i][j] * ans[j];
}
for (int i = 1; i <= m; i++) Mp[eg[i].first][eg[i].second] = Mp[eg[i].second][eg[i].first] = ans[i] + 0.5;
#ifdef _DEBUG_
for (int i = 1; i <= 5; i++, cerr << endl) for (int j = 1; j <= 5; j++) cerr << Mp[i][j] << ' ';
#endif
}
}
int a[maxn], b, p[maxn];
vector<int> G[maxn]; bool vs[maxn];
vector<vector<int> > sk, Sk;
inline int _ask(int u, int x, int y) { return ask(u, a[x], a[y]) - Mp[a[x]][a[y]]; }
void dfs(int x, int u, int val)
{
// cerr << x << ' ' << u << ' ' << val << endl;
if (vs[x]) { assert(val == Mp[a[x]][u]); return; } vs[x] = 1, Mp[a[x]][u] = Mp[u][a[x]] = val;
for (int y : G[x]) dfs(y, u, val ^ 1);
}
int main()
{
#ifdef _DEBUG_
for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) scanf("%d", &mp[i][j]), mp[j][i] = mp[i][j];
#endif
Solve5::solve();
for (int i = 1; i <= 5; i++) a[++b] = i;
for (int i = 6; i <= n; i++) p[i] = i; // shuffle(p + 6, p + n + 1, rnd);
for (int I = 6; I <= n; I++)
{
int u = p[I], fl = 0;
memset(vs, 0, sizeof vs);
shuffle(a + 1, a + b + 1, rnd);
for (int i = 1; i <= b; i++) G[i].clear(); sk.clear();
for (int i = 1; i <= b; i++) sk.push_back({ i });
while (sk.size() > 1)
{
// cerr << "[" << endl;
Sk.clear();
for (int i = 0, j; i + 1 < sk.size(); i += 2)
{
j = i + 1;
int v = sk[i][rnd() % sk[i].size()];
int w = sk[j][rnd() % sk[j].size()];
int h = _ask(u, v, w);
if (h == 0) dfs(v, u, 0), dfs(w, u, 0), fl = v;
else if (h == 2) dfs(v, u, 1), dfs(w, u, 1), fl = v;
else
{
G[v].push_back(w), G[w].push_back(v);
Sk.push_back(sk[i]);
Sk.back().insert(Sk.back().end(), sk[j].begin(), sk[j].end());
assert(Sk.back().size() == sk[i].size() + sk[j].size());
}
}
if (sk.size() & 1) Sk.push_back(sk.back());
sk = Sk;
// cerr << "]" << endl;
}
if (sk.size() == 1)
{
if (fl)
{
int v = sk[0][0];
dfs(v, u, _ask(u, v, fl) - Mp[a[fl]][u]);
}
else
{
assert(sk[0].size() >= 3);
int v = -1; for (int x : sk[0]) if (G[x].size() == 1) v = x; assert(v != -1);
int t = G[v][0];
int w = -1; for (int x : G[t]) if (x != v) w = x; assert(w != -1);
int h = _ask(u, v, w);
assert(h != 1);
if (h == 0) dfs(v, u, 0); else dfs(v, u, 1);
}
}
a[++b] = u;
}
#ifdef _DEBUG_
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (mp[i][j] != Mp[i][j]) cerr << i << ' ' << j << endl, assert(Mp[i][j] == mp[i][j]);
#else
printf("!\n");
for (int i = 1; i <= n; i++, puts("")) for (int j = 1; j <= n; j++) putchar(Mp[i][j] + '0');
#endif
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 100
Accepted
time: 5ms
memory: 3824kb
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 ? 6 3 4 ? 6 1 5 ? 6 2 1 ? 7 2 4 ? 7 1 3 ? 7 5 6 ? 8 2 6 ? 8 1 5 ? 8 4 3 ? 8 7 4 ? 9 3 2 ? 9 6 8 ? 9 4 5 ? 9 7 1 ? 10 5 3 ? 10 2 9 ? 10 7 1 ? 10 6 4 ? 10 8 6 ? 11 7 10 ? 11 8 4 ? 11 9 6 ? 11 2 3 ? 11 1 5 ? 12 11 8 ? 12 1 ...
result:
points 1.0 points 1.0 correct 2504 queries
Test #2:
score: 100
Accepted
time: 4ms
memory: 3832kb
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 ? 6 3 4 ? 6 1 5 ? 6 2 1 ? 7 2 4 ? 7 1 3 ? 7 5 6 ? 8 2 6 ? 8 1 5 ? 8 4 3 ? 8 7 4 ? 9 3 2 ? 9 6 8 ? 9 4 5 ? 9 7 1 ? 10 5 3 ? 10 2 9 ? 10 7 1 ? 10 6 4 ? 10 8 6 ? 11 7 10 ? 11 8 4 ? 11 9 6 ? 11 2 3 ? 11 1 5 ? 12 11 8 ? 12 1 ...
result:
points 1.0 points 1.0 correct 2504 queries
Test #3:
score: 100
Accepted
time: 5ms
memory: 3824kb
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 ? 6 3 4 ? 6 1 5 ? 6 2 1 ? 7 2 4 ? 7 1 3 ? 7 5 6 ? 8 2 6 ? 8 1 5 ? 8 4 3 ? 8 7 4 ? 9 3 2 ? 9 6 8 ? 9 4 5 ? 9 7 1 ? 10 5 3 ? 10 2 9 ? 10 7 1 ? 10 6 4 ? 10 8 6 ? 11 7 10 ? 11 8 4 ? 11 9 6 ? 11 2 3 ? 11 1 5 ? 12 11 8 ? 12 1 ...
result:
points 1.0 points 1.0 correct 2505 queries
Test #4:
score: 100
Accepted
time: 0ms
memory: 4088kb
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 ? 6 3 4 ? 6 1 5 ? 6 2 1 ? 7 2 4 ? 7 1 3 ? 7 5 6 ? 8 2 6 ? 8 1 5 ? 8 4 3 ? 8 7 4 ? 9 3 2 ? 9 6 8 ? 9 4 5 ? 9 7 1 ? 10 5 3 ? 10 2 9 ? 10 7 1 ? 10 6 4 ? 10 8 6 ? 11 7 10 ? 11 8 4 ? 11 9 6 ? 11 2 3 ? 11 1 5 ? 12 11 8 ? 12 1 ...
result:
points 1.0 points 1.0 correct 2505 queries
Test #5:
score: 100
Accepted
time: 3ms
memory: 3776kb
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 1 0 0 0 0 0 0 0 0 1 1 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 ? 6 3 4 ? 6 1 5 ? 6 2 1 ? 7 2 4 ? 7 1 3 ? 7 5 6 ? 8 2 6 ? 8 1 5 ? 8 4 3 ? 8 7 4 ? 9 3 2 ? 9 6 8 ? 9 4 5 ? 9 7 1 ? 10 5 3 ? 10 2 9 ? 10 7 1 ? 10 6 4 ? 10 8 6 ? 11 7 10 ? 11 8 4 ? 11 9 6 ? 11 2 3 ? 11 1 5 ? 12 11 8 ? 12 1 ...
result:
points 1.0 points 1.0 correct 2511 queries
Test #6:
score: 100
Accepted
time: 0ms
memory: 3820kb
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 2 2 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 ? 6 3 4 ? 6 1 5 ? 6 2 1 ? 7 2 4 ? 7 1 3 ? 7 5 6 ? 8 2 6 ? 8 1 5 ? 8 4 3 ? 8 7 4 ? 9 3 2 ? 9 6 8 ? 9 4 5 ? 9 7 1 ? 10 5 3 ? 10 2 9 ? 10 7 1 ? 10 6 4 ? 10 8 6 ? 11 7 10 ? 11 8 4 ? 11 9 6 ? 11 2 3 ? 11 1 5 ? 12 11 8 ? 12 1 ...
result:
points 1.0 points 1.0 correct 2509 queries
Test #7:
score: 100
Accepted
time: 6ms
memory: 3836kb
input:
0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 1 1 2 1 0 0 0 2 1 1 1 0 0 1 1 1 0 2 2 3 1 0 0 1 0 1 0 2 2 1 0 0 0 0 1 1 1 1 1 2 2 0 0 0 2 2 2 1 2 1 0 1 1 1 1 1 2 0 0 1 1 0 1 0 1 1 0 2 0 1 1 0 2 1 2 1 1 0 1 2 2 0 0 1 1 2 1 0 2 2 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 2 1 0 1 1 1 2 2 1 1 1 1 0 1 1 2 1 0 1 1 ...
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 ? 6 3 4 ? 6 1 5 ? 6 4 2 ? 7 1 2 ? 7 4 3 ? 7 5 6 ? 7 1 6 ? 7 1 4 ? 8 7 3 ? 8 5 4 ? 8 6 1 ? 8 4 6 ? 8 2 4 ? 9 7 3 ? 9 8 1 ? 9 4 2 ? 9 5 6 ? 9 4 5 ? 10 8 6 ? 10 5 4 ? 10 2 3 ? 10 1 7 ? 10 7 9 ? 10 1 2 ? 11 1 3 ? 11 2 5 ? 11...
result:
points 1.0 points 1.0 correct 3064 queries
Test #8:
score: 0
Wrong Answer
time: 5ms
memory: 4100kb
input:
3 1 2 1 2 1 1 1 0 0 0 1 1 1 2 1 1 1 0 1 1 0 1 1 1 2 2 1 0 1 1 1 0 1 0 1 0 2 1 3 1 0 1 1 0 1 2 1 0 1 1 2 2 0 0 1 0 0 0 2 2 3 1 0 0 1 0 0 2 2 1 2 2 2 2 1 2 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 0 2 2 1 2 1 2 1 1 3 1 1 3 1 1 3 1 1 1 0 2 2 1 2 2 2 0 0 1 0 1 2 1 2 1 1 1 1 0 2 2 3 0 1 1 0 1 3 1 1 3 0 2 2 1 2 0 1 ...
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 ? 6 3 4 ? 6 1 5 ? 6 2 1 ? 7 2 4 ? 7 1 3 ? 7 5 6 ? 7 1 6 ? 7 1 2 ? 8 4 6 ? 8 2 1 ? 8 7 5 ? 8 5 3 ? 9 4 2 ? 9 1 7 ? 9 5 3 ? 9 6 8 ? 9 1 5 ? 9 1 6 ? 10 1 8 ? 10 6 5 ? 10 3 2 ? 10 7 4 ? 10 5 3 ? 10 4 9 ? 10 7 5 ? 11 9 10 ? 1...
result:
wrong answer Token parameter [name=ans_i] equals to "011010000010101101201020100100...010000110111000001000/010000100", doesn't correspond to pattern "[01]{100,100}"