QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#800649#8871. Interactive Reconstructionphtniit#AC ✓63ms5660kbC++141.1kb2024-12-06 13:50:592024-12-06 13:51:00

Judging History

This is the latest submission verdict.

  • [2024-12-06 13:51:00]
  • Judged
  • Verdict: AC
  • Time: 63ms
  • Memory: 5660kb
  • [2024-12-06 13:50:59]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
using vi = vector<int>;
using i64 = long long;

auto Q(string s) {
  printf("QUERY %s\n", s.c_str());
  fflush(stdout);
  vi vt(s.size());
  for (int i = 0; i < vt.size(); ++i) scanf("%d", &vt[i]);
  return vt;
}

int main() {
  int n;
  scanf("%d", &n);
  string s(n, '1');
  auto deg = Q(s);
  vector<i64> sum(n, 0);
  for (int i = 0; i < 15; ++i) {
    s = string(n, '0');
    for (int j = 0; j < n; ++j) {
      if ((j+1) & (1<<i)) {
        s[j] = '1';
      }
    }
    auto f = Q(s);
    for (int j = 0; j < n; ++j) sum[j] += f[j] * (1<<i);
  }
  queue<int> q;
  for (int i = 0; i < n; ++i) if (deg[i] == 1) {
    q.push(i);
  }
  set<pii> E;
  while (not q.empty()) {
    auto u = q.front(); q.pop();
    int v = sum[u] - 1;
    E.emplace(min(u, v), max(u, v));
    if (deg[v] > 1) {
      sum[v] -= (u+1);
      deg[v]--;
      if (deg[v] == 1) {
        q.push(v);
      }
    }
  }
  assert(E.size() == n-1);
  puts("ANSWER");
  for (auto [u,v]: E) printf("%d %d\n", u+1, v+1);
  fflush(stdout);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 61ms
memory: 5652kb

input:

30000
1 1 3 3 1 3 1 1 3 1 3 1 1 3 3 3 3 1 3 3 1 3 3 1 3 1 1 1 3 3 3 3 3 1 1 3 3 3 1 3 3 3 1 3 3 3 3 1 1 3 3 1 3 3 3 1 1 1 3 1 1 3 1 1 3 1 3 1 3 1 3 3 3 3 1 3 1 1 1 3 3 1 3 3 3 3 1 3 1 3 1 3 3 3 3 1 1 3 3 1 3 3 3 1 3 3 1 3 3 3 1 1 3 1 1 1 1 1 3 1 3 1 3 1 1 3 3 3 3 3 3 3 1 1 1 3 1 1 3 3 3 1 1 1 3 1 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #2:

score: 0
Accepted
time: 28ms
memory: 4844kb

input:

16384
1 3 3 3 3 3 1 1 3 1 3 3 3 3 3 1 1 1 1 3 3 3 3 3 1 1 3 1 1 1 3 3 3 3 1 1 1 3 3 1 3 3 3 3 1 1 1 3 1 3 3 1 3 1 3 1 1 3 1 3 3 1 3 1 1 3 1 3 1 3 3 3 3 1 1 1 1 1 1 1 1 3 3 1 1 1 3 1 3 1 1 3 1 3 1 1 1 1 3 1 1 3 1 1 3 3 3 1 1 3 1 3 1 1 1 1 3 1 1 1 3 3 1 3 1 3 3 1 1 1 3 3 3 1 1 1 1 1 3 1 1 1 3 1 3 1 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #3:

score: 0
Accepted
time: 0ms
memory: 4084kb

input:

8
1 3 2 1 3 1 1 2
0 3 1 1 1 0 0 1
1 2 1 0 1 0 1 1
0 1 1 1 1 0 0 2
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 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
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:

QUERY 11111111
QUERY 10101010
QUERY 01100110
QUERY 00011110
QUERY 00000001
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
ANSWER
1 2
2 3
2 7
3 5
4 5
5 8
6 8

result:

ok correct answer

Test #4:

score: 0
Accepted
time: 1ms
memory: 4096kb

input:

4
1 1 1 3
0 0 0 2
0 0 0 2
1 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 0
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:

QUERY 1111
QUERY 1010
QUERY 0110
QUERY 0001
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
ANSWER
1 4
2 4
3 4

result:

ok correct answer

Test #5:

score: 0
Accepted
time: 57ms
memory: 5388kb

input:

30000
1 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 1 2 2 2 2 2 2 3 2 3 2 2 2 2 4 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 2 2 2 3 2 2 2 2 2 2 2 1 2 2 2 1 3 1 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 1 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 1 2 3 2 3 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #6:

score: 0
Accepted
time: 63ms
memory: 5384kb

input:

29999
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 1 2 2 2 3 2 2 2 2 2 2 2 2 2 3 2 3 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 2 2 2 4 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 1 2 2 1 2 2 2 2 2 2 2 2 1 2 1 2 2 2 2 2 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #7:

score: 0
Accepted
time: 52ms
memory: 5428kb

input:

30000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #8:

score: 0
Accepted
time: 58ms
memory: 5364kb

input:

29997
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #9:

score: 0
Accepted
time: 1ms
memory: 4108kb

input:

8
2 2 2 1 2 2 1 2
0 1 1 1 1 2 0 1
1 1 1 0 1 1 1 1
2 1 2 0 0 0 0 1
0 1 0 0 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 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
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:

QUERY 11111111
QUERY 10101010
QUERY 01100110
QUERY 00011110
QUERY 00000001
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
ANSWER
1 4
1 6
2 7
2 8
3 5
3 6
5 8

result:

ok correct answer

Test #10:

score: 0
Accepted
time: 61ms
memory: 5376kb

input:

30000
2 2 1 4 10 4 3 1 1 1 1 1 4 1 1 1 2 4 2 3 1 2 4 1 1 3 1 5 1 1 5 3 1 1 2 2 1 4 1 3 3 2 2 2 2 1 1 2 3 4 3 4 1 2 2 3 1 1 1 1 1 1 3 2 1 2 2 1 1 2 1 2 2 2 1 1 3 1 4 1 2 1 3 2 1 2 1 1 1 3 1 7 2 1 2 1 1 6 2 1 5 4 1 1 2 1 1 1 3 1 1 1 1 1 1 4 3 3 2 1 2 1 2 1 1 1 5 1 4 2 1 1 1 1 4 1 1 2 1 7 2 1 1 1 1 1 1...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #11:

score: 0
Accepted
time: 52ms
memory: 5380kb

input:

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

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #12:

score: 0
Accepted
time: 60ms
memory: 5372kb

input:

30000
1 4 1 1 2 1 1 1 1 1 2 1 2 1 1 2 1 1 1 3 1 1 1 7 3 2 5 1 1 9 1 1 4 1 1 4 2 1 2 1 1 1 3 3 1 1 1 1 2 4 4 6 1 2 2 1 1 1 2 2 2 1 2 1 3 3 3 2 1 1 1 1 1 1 1 4 2 1 2 1 1 2 1 3 5 1 1 2 2 1 2 3 1 3 1 1 1 2 1 2 2 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 2 4 2 3 1 2 2 2 3 2 1 2 3 1 1 2 1 1 3 1 1 5 2 1 1 2 2 1 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #13:

score: 0
Accepted
time: 56ms
memory: 5396kb

input:

29997
5 1 1 1 2 5 1 1 3 1 3 1 5 2 1 1 2 2 4 2 1 4 2 1 4 1 1 2 1 1 1 2 1 1 2 8 1 4 4 1 2 3 2 1 3 1 2 2 2 5 1 4 2 2 3 2 2 2 3 3 2 2 7 4 4 4 1 5 5 2 1 4 1 1 2 2 5 1 1 3 3 1 3 1 1 1 1 2 1 4 3 4 3 2 1 2 2 1 1 1 2 1 3 1 1 1 2 2 2 2 1 2 4 4 3 2 1 3 1 2 1 2 1 1 3 3 3 2 3 2 1 1 2 1 1 1 1 2 2 1 1 2 2 1 1 1 6 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #14:

score: 0
Accepted
time: 1ms
memory: 4080kb

input:

10
2 1 3 2 1 1 2 2 1 3
0 0 2 1 0 1 1 2 1 1
1 1 1 2 0 1 2 0 1 1
0 0 2 0 0 1 1 1 0 1
2 1 1 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 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 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:

QUERY 1111111111
QUERY 1010101010
QUERY 0110011001
QUERY 0001111000
QUERY 0000000111
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
ANSWER
1 8
1 10
2 10
3 4
3 7...

result:

ok correct answer

Test #15:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

8
1 1 2 3 4 1 1 1
1 1 2 2 1 1 0 0
1 0 0 1 3 0 0 0
0 1 1 2 2 1 1 1
0 0 0 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 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
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:

QUERY 11111111
QUERY 10101010
QUERY 01100110
QUERY 00011110
QUERY 00000001
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
ANSWER
1 3
2 5
3 5
4 5
4 7
4 8
5 6

result:

ok correct answer

Test #16:

score: 0
Accepted
time: 52ms
memory: 5408kb

input:

30000
2 1 2 3 1 1 5 3 1 5 3 1 4 1 3 1 1 1 1 2 1 1 1 1 6 2 2 2 1 3 1 6 3 4 1 3 1 1 2 1 1 1 1 3 1 3 1 2 1 1 1 1 1 5 3 5 1 3 1 1 1 1 1 4 2 3 1 1 1 1 3 1 2 1 1 1 1 3 4 1 2 2 1 2 3 1 1 2 1 1 1 2 1 1 1 1 1 1 1 2 2 1 2 2 2 1 3 3 3 4 2 4 2 1 2 1 1 4 1 2 3 4 1 1 1 1 1 2 1 2 1 1 2 6 3 1 2 1 1 3 1 2 2 1 1 2 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #17:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

128
1 2 2 7 3 1 2 2 3 4 1 4 1 1 3 1 1 1 4 3 2 1 3 1 2 1 5 1 2 2 3 1 1 3 3 2 1 1 1 3 1 3 1 1 1 2 3 3 4 3 2 1 7 1 4 1 1 4 4 3 1 3 2 1 2 1 1 1 2 1 1 1 1 1 1 2 3 1 1 1 1 2 2 1 1 1 1 3 2 1 1 1 3 1 1 1 3 2 2 1 3 3 1 3 4 1 1 1 7 1 1 4 1 1 3 2 1 2 2 2 1 6 2 1 1 2 1 1
0 1 0 2 2 1 1 2 1 1 1 4 1 0 3 0 1 0 1 2 ...

output:

QUERY 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
QUERY 10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
QUERY 011001100110011001100110...

result:

ok correct answer

Test #18:

score: 0
Accepted
time: 51ms
memory: 5660kb

input:

30000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #19:

score: 0
Accepted
time: 1ms
memory: 4108kb

input:

3
1 1 2
1 1 1
1 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
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0

output:

QUERY 111
QUERY 101
QUERY 011
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
ANSWER
1 3
2 3

result:

ok correct answer

Test #20:

score: 0
Accepted
time: 1ms
memory: 3808kb

input:

2
1 1
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 0
0 0

output:

QUERY 11
QUERY 10
QUERY 01
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
ANSWER
1 2

result:

ok correct answer