QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116933#6668. TrokutiLinshey#0 6ms4100kbC++144.7kb2023-06-30 10:56:572024-05-31 18:35:03

Judging History

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

  • [2024-05-31 18:35:03]
  • 评测
  • 测评结果:0
  • 用时:6ms
  • 内存:4100kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-30 10:56:57]
  • 提交

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}"