QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#520022	#6668. Trokuti	bykem	100 ✓	14ms	3756kb	C++20	2.8kb	2024-08-15 10:16:47	2024-08-15 10:16:48

Judging History

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

[2024-08-15 10:16:48]
评测

测评结果：100
用时：14ms
内存：3756kb

查看

[2024-08-15 10:16:47]
提交

answer

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

using namespace std;

mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());

const int kN = 101;
const int kM[10][10] = {{2, 2, 2, -1, -1, -1, -1, -1, -1, 2}, {2, -1, -1, 2, 2, -1, -1, -1, 2, -1}, {-1, 2, -1, 2, -1, 2, -1, 2, -1, -1}, {-1, -1, 2, -1, 2, 2, 2, -1, -1, -1}, {2, -1, -1, -1, -1, 2, 2, 2, -1, -1}, {-1, 2, -1, -1, 2, -1, 2, -1, 2, -1}, {-1, -1, 2, 2, -1, -1, -1, 2, 2, -1}, {-1, -1, 2, 2, -1, -1, 2, -1, -1, 2}, {-1, 2, -1, -1, 2, -1, -1, 2, -1, 2}, {2, -1, -1, -1, -1, 2, -1, -1, 2, 2}};

int n = kN - 1;
bool e[kN][kN];
vector<int> p;
int b[10];

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  for (int i = 1, c = 0; i <= 5; ++i) {
    for (int j = i + 1; j <= 5; ++j) {
      for (int k = j + 1; k <= 5; ++k) {
        cout << "? " << i << ' ' << j << ' ' << k << endl;
        cin >> b[c++];
      }
    }
  }
  for (int i = 1, c = 0; i <= 5; ++i) {
    for (int j = i + 1; j <= 5; ++j) {
      int s = 0;
      for (int k = 0; k < 10; ++k) {
        s += b[k] * kM[c][k];
      }
      e[i][j] = e[j][i] = s / 6;
      ++c;
    }
  }
  p = {1, 2, 3, 4, 5};
  for (int i = 6; i <= n; ++i) {
    shuffle(p.begin(), p.end(), rnd);
    int j = 0;
    for (; j + 1 < p.size();) {
      int r = j;
      for (; r + 1 < p.size(); ++r) {
        cout << "? " << i << ' ' << p[r] << ' ' << p[r + 1] << endl;
        int v;
        cin >> v;
        v -= e[p[r]][p[r + 1]];
        if (v != 1) {
          e[i][p[r]] = e[i][p[r + 1]] = v / 2;
          e[p[r]][i] = e[p[r + 1]][i] = v / 2;
          break;
        }
      }
      if (r == p.size() - 1) {
        if (j) {
          cout << "? " << i << ' ' << p[0] << ' ' << p[j] << endl;
          int v;
          cin >> v;
          v -= e[i][p[0]] + e[p[0]][p[j]];
          for (int k = j; k < p.size(); ++k) {
            e[i][p[k]] = e[p[k]][i] = v ^ (k - j & 1);
          }
        } else {
          cout << "? " << i << ' ' << p[0] << ' ' << p[2] << endl;
          int v;
          cin >> v;
          v = (v - e[p[0]][p[2]]) / 2;
          for (int k = 0; k < p.size(); ++k) {
            e[i][p[k]] = e[p[k]][i] = v ^ (k & 1);
          }
        }
        break;
      }
      for (int k = r; k > j; --k) {
        e[i][p[k - 1]] = e[p[k - 1]][i] = !e[i][p[k]];
      }
      j = r + 2;
    }
    if (j == p.size() - 1) {
      cout << "? " << i << ' ' << p[0] << ' ' << p[j] << endl;
      int v;
      cin >> v;
      e[i][p[j]] = e[p[j]][i] = v - e[i][p[0]] - e[p[0]][p[j]];
    }
    p.push_back(i);
  }
  cout << '!' << endl;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cout << e[i][j];
    }
    cout << '\n';
  }
  cout.flush();
  return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 100

Accepted

Test #1:

score: 100

Accepted

time: 11ms

memory: 3656kb

input:

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 4 5
? 6 1 3
? 6 4 2
? 7 2 4
? 7 1 6
? 7 5 3
? 8 2 6
? 8 1 7
? 8 3 4
? 8 2 5
? 9 4 5
? 9 8 7
? 9 2 1
? 9 6 3
? 10 6 2
? 10 3 8
? 10 5 1
? 10 4 9
? 10 6 7
? 11 10 4
? 11 3 9
? 11 2 5
? 11 1 7
? 11 8 6
? 12 1 5
? 12 11 ...

result:

points 1.0 points  1.0 correct 2504 queries

Test #2:

score: 100

Accepted

time: 8ms

memory: 3728kb

input:

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 2
? 6 1 4
? 6 3 5
? 7 4 5
? 7 1 3
? 7 6 2
? 8 4 5
? 8 1 7
? 8 2 3
? 8 4 6
? 9 3 8
? 9 1 4
? 9 6 7
? 9 2 5
? 10 2 6
? 10 5 1
? 10 8 3
? 10 4 7
? 10 2 9
? 11 9 3
? 11 8 4
? 11 1 6
? 11 5 2
? 11 7 10
? 12 6 1
? 12 5 3...

result:

points 1.0 points  1.0 correct 2504 queries

Test #3:

score: 100

Accepted

time: 14ms

memory: 3672kb

input:

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 5 2
? 6 1 3
? 6 5 4
? 7 5 6
? 7 3 2
? 7 1 4
? 8 1 2
? 8 5 7
? 8 4 6
? 8 1 3
? 9 4 1
? 9 8 7
? 9 6 5
? 9 3 2
? 10 6 3
? 10 2 9
? 10 7 1
? 10 4 5
? 10 6 8
? 11 1 4
? 11 10 6
? 11 7 8
? 11 2 9
? 11 3 5
? 12 5 7
? 12 6 9...

result:

points 1.0 points  1.0 correct 2505 queries

Test #4:

score: 100

Accepted

time: 3ms

memory: 3660kb

input:

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 2 1
? 6 3 4
? 6 2 5
? 7 1 2
? 7 5 6
? 7 3 4
? 8 7 6
? 8 4 3
? 8 5 1
? 8 7 2
? 9 8 5
? 9 2 6
? 9 7 1
? 9 4 3
? 10 5 4
? 10 7 9
? 10 3 1
? 10 2 8
? 10 5 6
? 11 4 7
? 11 10 8
? 11 1 9
? 11 5 6
? 11 2 3
? 12 2 1
? 12 4 1...

result:

points 1.0 points  1.0 correct 2505 queries

Test #5:

score: 100

Accepted

time: 0ms

memory: 3740kb

input:

output:

result:

points 1.0 points  1.0 correct 2511 queries

Test #6:

score: 100

Accepted

time: 0ms

memory: 3672kb

input:

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 5 4
? 6 2 1
? 6 5 3
? 7 6 4
? 7 2 3
? 7 1 5
? 8 5 3
? 8 1 6
? 8 7 2
? 8 5 4
? 9 3 8
? 9 4 1
? 9 6 7
? 9 2 5
? 10 6 4
? 10 1 5
? 10 2 3
? 10 9 7
? 10 6 8
? 11 7 5
? 11 4 3
? 11 8 9
? 11 2 6
? 11 10 1
? 12 9 4
? 12 1 5...

result:

points 1.0 points  1.0 correct 2510 queries

Test #7:

score: 100

Accepted

time: 0ms

memory: 3756kb

input:

output:

result:

points 1.0 points  1.0 correct 3141 queries

Test #8:

score: 100

Accepted

time: 3ms

memory: 3668kb

input:

output:

result:

points 1.0 points  1.0 correct 3279 queries

Test #9:

score: 100

Accepted

time: 5ms

memory: 3752kb

input:

output:

result:

points 1.0 points  1.0 correct 3333 queries

Test #10:

score: 100

Accepted

time: 4ms

memory: 3652kb

input:

output:

result:

points 1.0 points  1.0 correct 3014 queries

Test #11:

score: 100

Accepted

time: 0ms

memory: 3668kb

input:

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 2 4
? 6 4 5
? 6 5 3
? 6 2 1
? 7 2 3
? 7 3 4
? 7 1 5
? 7 5 6
? 7 2 1
? 8 1 3
? 8 3 5
? 8 5 4
? 8 4 7
? 8 6 2
? 8 1 6
? 9 8 3
? 9 1 7
? 9 7 2
? 9 2 6
? 9 6 5
? 9 5 4
? 9 8 1
? 10 1 6
? 10 7 2
? 10 9 8
? 10 8 4
? 10 5 3...

result:

points 1.0 points  1.0 correct 3322 queries

Test #12:

score: 100

Accepted

time: 4ms

memory: 3756kb

input:

output:

result:

points 1.0 points  1.0 correct 3295 queries

Test #13:

score: 100

Accepted

time: 12ms

memory: 3676kb

input:

output:

result:

points 1.0 points  1.0 correct 3320 queries

Test #14:

score: 100

Accepted

time: 0ms

memory: 3612kb

input:

output:

result:

points 1.0 points  1.0 correct 3356 queries

Test #15:

score: 100

Accepted

time: 0ms

memory: 3616kb

input:

output:

result:

points 1.0 points  1.0 correct 3299 queries

Test #16:

score: 100

Accepted

time: 0ms

memory: 3672kb

input:

output:

result:

points 1.0 points  1.0 correct 3335 queries

Test #17:

score: 100

Accepted

time: 9ms

memory: 3604kb

input:

output:

result:

points 1.0 points  1.0 correct 3353 queries

Test #18:

score: 100

Accepted

time: 7ms

memory: 3676kb

input:

output:

result:

points 1.0 points  1.0 correct 3310 queries

Test #19:

score: 100

Accepted

time: 8ms

memory: 3604kb

input:

output:

result:

points 1.0 points  1.0 correct 3302 queries

Test #20:

score: 100

Accepted

time: 12ms

memory: 3732kb

input:

output:

result:

points 1.0 points  1.0 correct 3344 queries