QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#99801#6345. Random Interactive Convex Hull BotwhateverAC ✓188ms3504kbC++171.4kb2023-04-23 19:19:122023-04-23 19:20:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-23 19:20:05]
  • 评测
  • 测评结果:AC
  • 用时:188ms
  • 内存:3504kb
  • [2023-04-23 19:19:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a, I = b; i <= I; ++i)
#define per(i, a, b) for (int i = a, I = b; i >= I; --i)
using i64 = long long;
using i128 = __int128_t;
using pii = pair<i64, i64>;
template<typename T> void up(T &x, T y) { if (x < y) x = y; }
template<typename T> void down(T &x, T y) { if (x > y) x = y; }

int query(int i, int j, int k) {
    cout << "? " << i << " " << j << " " << k << endl;
    int res; cin >> res; return res == 1;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    int n; cin >> n;
    vector<int> nodes{1, 2, 3};
    if (!query(1, 2, 3)) swap(nodes[1], nodes[2]);

    rep(i, 4, n) {
        int m = nodes.size();
        int l = 0, r = m - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (query(nodes[0], nodes[mid], i)) l = mid;
            else r = mid - 1;
        }
        if (l > 0 && l < m - 1 && query(nodes[l], nodes[l + 1], i)) continue;
        rotate(nodes.begin(), nodes.begin() + l + 1, nodes.end());       
        while ((int) nodes.size() > 2 && query(i, nodes[1], nodes[0])) nodes.erase(nodes.begin());
        while ((int) nodes.size() > 2 && query(i, nodes.back(), nodes[(int) nodes.size() - 2])) nodes.erase(--nodes.end());
        nodes.insert(nodes.begin(), i);
    }

    cout << "! " << nodes.size();
    for (auto x : nodes) cout << " " << x;
    cout << endl;
    
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3428kb

input:

5
-1
-1
1
-1
-1
-1

output:

? 1 2 3
? 1 3 4
? 4 2 3
? 4 2 5
? 5 1 2
? 5 4 1
! 4 5 2 1 4

result:

ok OK, 6 queries, 4 point in hull

Test #2:

score: 0
Accepted
time: 11ms
memory: 3352kb

input:

50
-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:

? 1 2 3
? 1 3 4
? 1 2 4
? 4 3 1
? 4 2 3
? 4 3 5
? 4 2 5
? 3 2 5
? 5 4 2
? 5 3 1
? 5 4 6
? 5 2 6
? 6 4 2
? 6 5 3
? 6 1 7
? 6 3 7
? 1 3 7
? 7 5 3
? 7 1 4
? 7 6 8
? 7 3 8
? 7 5 8
? 3 5 8
? 8 6 5
? 8 2 6
? 8 3 7
? 8 4 9
? 8 6 9
? 8 2 9
? 2 4 9
? 9 1 4
? 9 2 6
? 9 3 10
? 9 6 10
? 9 8 10
? 3 8 10
? 9 3 11...

result:

ok OK, 234 queries, 10 point in hull

Test #3:

score: 0
Accepted
time: 12ms
memory: 3388kb

input:

1000
-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:

? 1 2 3
? 1 3 4
? 1 2 4
? 4 3 1
? 4 2 3
? 4 3 5
? 4 1 5
? 5 3 1
? 5 4 2
? 5 2 3
? 5 3 6
? 5 2 6
? 6 1 5
? 6 3 1
? 6 2 3
? 6 3 7
? 6 2 7
? 7 1 6
? 7 2 3
? 7 1 8
? 7 3 8
? 7 2 8
? 3 2 8
? 7 1 9
? 7 6 9
? 9 1 6
? 9 7 2
? 9 2 3
? 9 1 10
? 9 3 10
? 9 2 10
? 10 6 9
? 10 2 3
? 10 1 11
? 10 9 11
? 10 6 11
?...

result:

ok OK, 5144 queries, 21 point in hull

Test #4:

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

input:

2000
-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:

? 1 2 3
? 1 3 4
? 1 2 4
? 3 2 4
? 4 1 2
? 4 3 1
? 4 1 5
? 4 3 5
? 5 2 4
? 5 3 1
? 5 2 6
? 5 1 6
? 5 3 6
? 1 3 6
? 6 5 3
? 6 1 2
? 6 4 7
? 6 3 7
? 6 5 7
? 5 4 7
? 7 2 4
? 7 1 2
? 7 5 3
? 7 6 8
? 7 3 8
? 6 3 8
? 7 6 9
? 7 2 9
? 7 1 9
? 1 6 9
? 7 6 10
? 7 3 10
? 7 5 10
? 10 2 7
? 10 5 3
? 10 1 11
? 10 ...

result:

ok OK, 10872 queries, 23 point in hull

Test #5:

score: 0
Accepted
time: 84ms
memory: 3424kb

input:

3000
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:

? 1 2 3
? 1 2 4
? 4 3 2
? 4 1 3
? 4 3 5
? 4 2 5
? 5 3 2
? 5 1 3
? 5 4 1
? 5 1 6
? 5 3 6
? 3 1 6
? 6 4 1
? 6 5 4
? 6 3 5
? 6 5 7
? 6 3 7
? 7 4 6
? 7 5 4
? 7 3 5
? 7 5 8
? 7 4 8
? 8 5 4
? 8 7 3
? 8 5 9
? 8 4 9
? 9 5 4
? 9 8 7
? 9 3 10
? 9 4 10
? 10 5 4
? 10 9 8
? 10 3 11
? 10 8 11
? 10 9 11
? 11 4 10
...

result:

ok OK, 15868 queries, 25 point in hull

Test #6:

score: 0
Accepted
time: 59ms
memory: 3484kb

input:

4000
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:

? 1 2 3
? 1 2 4
? 4 3 2
? 4 1 3
? 4 3 5
? 4 2 5
? 2 3 5
? 5 1 3
? 5 4 1
? 5 2 4
? 5 4 6
? 5 2 6
? 4 2 6
? 5 4 7
? 5 1 7
? 1 4 7
? 5 4 8
? 5 2 8
? 4 2 8
? 5 4 9
? 5 2 9
? 4 2 9
? 5 4 10
? 5 2 10
? 10 1 5
? 10 2 4
? 10 1 11
? 10 4 11
? 10 2 11
? 11 5 10
? 11 2 4
? 11 4 1
? 11 5 12
? 11 1 12
? 11 4 12
...

result:

ok OK, 21307 queries, 22 point in hull

Test #7:

score: 0
Accepted
time: 132ms
memory: 3392kb

input:

4999
-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:

? 1 2 3
? 1 3 4
? 4 2 3
? 4 1 2
? 4 2 5
? 4 1 5
? 5 3 4
? 5 2 3
? 5 1 2
? 5 2 6
? 5 1 6
? 6 3 5
? 6 1 2
? 6 3 7
? 6 5 7
? 5 3 7
? 6 3 8
? 6 2 8
? 3 2 8
? 6 3 9
? 6 2 9
? 6 1 9
? 9 5 6
? 9 1 2
? 9 2 3
? 9 5 10
? 9 6 10
? 10 5 6
? 10 9 2
? 10 3 11
? 10 6 11
? 10 5 11
? 6 5 11
? 11 3 5
? 11 6 10
? 11 2...

result:

ok OK, 27477 queries, 24 point in hull

Test #8:

score: 0
Accepted
time: 188ms
memory: 3432kb

input:

5000
-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:

? 1 2 3
? 1 3 4
? 1 2 4
? 4 3 1
? 4 2 3
? 4 3 5
? 4 1 5
? 5 3 1
? 5 4 2
? 5 3 6
? 5 2 6
? 3 2 6
? 6 4 2
? 6 5 4
? 6 3 1
? 6 5 7
? 6 4 7
? 7 5 4
? 7 1 5
? 7 6 3
? 7 1 8
? 7 3 8
? 7 6 8
? 3 6 8
? 7 1 9
? 7 5 9
? 9 1 5
? 9 3 1
? 9 7 6
? 9 3 10
? 9 6 10
? 3 6 10
? 9 3 11
? 9 6 11
? 3 6 11
? 9 3 12
? 9 6...

result:

ok OK, 27049 queries, 21 point in hull

Test #9:

score: 0
Accepted
time: 128ms
memory: 3448kb

input:

5000
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:

? 1 2 3
? 1 2 4
? 4 3 2
? 4 1 3
? 4 3 5
? 4 1 5
? 5 2 4
? 5 1 3
? 5 3 2
? 5 4 6
? 5 2 6
? 4 2 6
? 5 4 7
? 7 2 4
? 7 5 2
? 7 2 8
? 7 5 8
? 2 5 8
? 8 7 5
? 8 2 4
? 8 7 9
? 8 5 9
? 9 7 5
? 9 4 7
? 9 8 2
? 9 4 10
? 9 2 10
? 4 2 10
? 10 8 2
? 10 4 7
? 10 9 11
? 10 7 11
? 10 4 11
? 11 2 10
? 11 8 2
? 11 4...

result:

ok OK, 27446 queries, 27 point in hull

Test #10:

score: 0
Accepted
time: 98ms
memory: 3384kb

input:

5000
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:

? 1 2 3
? 1 2 4
? 4 3 2
? 4 1 3
? 4 2 5
? 4 3 5
? 5 2 4
? 5 3 2
? 5 2 6
? 5 3 6
? 2 3 6
? 6 5 3
? 6 2 4
? 6 5 7
? 6 3 7
? 7 5 3
? 7 4 5
? 7 6 2
? 7 2 4
? 7 4 8
? 7 2 8
? 4 2 8
? 7 4 9
? 7 2 9
? 4 2 9
? 7 4 10
? 7 5 10
? 10 4 5
? 10 2 4
? 10 7 2
? 10 2 11
? 10 4 11
? 4 2 11
? 10 2 12
? 10 4 12
? 4 2 ...

result:

ok OK, 28060 queries, 25 point in hull

Test #11:

score: 0
Accepted
time: 161ms
memory: 3460kb

input:

5000
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:

? 1 2 3
? 1 2 4
? 4 3 2
? 4 1 3
? 4 3 5
? 4 2 5
? 5 3 2
? 5 4 1
? 5 1 3
? 5 3 6
? 5 2 6
? 6 3 2
? 6 1 3
? 6 5 1
? 6 1 7
? 6 5 7
? 1 5 7
? 6 1 8
? 6 5 8
? 8 3 6
? 8 5 1
? 8 3 9
? 8 1 9
? 8 5 9
? 1 5 9
? 9 8 5
? 9 1 3
? 9 6 10
? 9 5 10
? 10 8 5
? 10 6 8
? 10 9 1
? 10 3 11
? 10 8 11
? 10 6 11
? 6 3 11
...

result:

ok OK, 27057 queries, 25 point in hull

Test #12:

score: 0
Accepted
time: 159ms
memory: 3348kb

input:

5000
-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:

? 1 2 3
? 1 3 4
? 1 2 4
? 3 2 4
? 4 1 2
? 4 3 1
? 4 1 5
? 4 2 5
? 2 1 5
? 4 1 6
? 4 2 6
? 6 1 2
? 6 4 3
? 6 1 7
? 6 3 7
? 6 4 7
? 3 4 7
? 6 1 8
? 6 2 8
? 8 1 2
? 8 3 1
? 8 6 4
? 8 3 9
? 8 4 9
? 3 4 9
? 8 3 10
? 8 1 10
? 1 3 10
? 10 4 3
? 10 1 8
? 10 6 11
? 10 3 11
? 10 4 11
? 3 4 11
? 11 6 4
? 11 3 ...

result:

ok OK, 27233 queries, 27 point in hull

Test #13:

score: 0
Accepted
time: 139ms
memory: 3420kb

input:

5000
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:

? 1 2 3
? 1 2 4
? 4 3 2
? 4 1 3
? 4 3 5
? 4 1 5
? 3 1 5
? 4 3 6
? 4 2 6
? 2 3 6
? 6 1 3
? 6 2 4
? 6 1 7
? 6 4 7
? 1 4 7
? 7 2 4
? 7 1 3
? 7 6 8
? 7 3 8
? 7 1 8
? 8 4 7
? 8 1 3
? 8 3 6
? 8 2 9
? 8 6 9
? 2 6 9
? 9 3 6
? 9 2 4
? 9 8 10
? 9 6 10
? 10 3 6
? 10 8 3
? 10 9 2
? 10 7 11
? 10 3 11
? 11 8 3
? ...

result:

ok OK, 28306 queries, 25 point in hull

Test #14:

score: 0
Accepted
time: 130ms
memory: 3476kb

input:

5000
-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:

? 1 2 3
? 1 3 4
? 4 2 3
? 4 1 2
? 4 2 5
? 4 3 5
? 3 2 5
? 4 2 6
? 4 1 6
? 2 1 6
? 6 4 1
? 6 2 3
? 6 4 7
? 6 1 7
? 7 4 1
? 7 3 4
? 7 6 2
? 7 2 3
? 7 3 8
? 7 4 8
? 8 3 4
? 8 7 2
? 8 3 9
? 8 4 9
? 9 3 4
? 9 8 7
? 9 7 2
? 9 3 10
? 9 2 10
? 3 2 10
? 9 3 11
? 9 4 11
? 4 3 11
? 11 2 3
? 11 4 9
? 11 7 12
? ...

result:

ok OK, 27699 queries, 28 point in hull

Test #15:

score: 0
Accepted
time: 129ms
memory: 3396kb

input:

5000
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:

? 1 2 3
? 1 2 4
? 1 3 4
? 4 2 1
? 4 3 2
? 4 1 5
? 5 2 1
? 5 4 2
? 5 2 6
? 5 4 6
? 6 1 5
? 6 4 2
? 6 1 7
? 6 2 7
? 6 4 7
? 7 5 6
? 7 4 2
? 7 2 1
? 7 5 8
? 7 1 8
? 7 2 8
? 1 2 8
? 8 7 2
? 8 1 5
? 8 6 9
? 8 2 9
? 8 7 9
? 7 6 9
? 8 6 10
? 8 5 10
? 8 1 10
? 10 2 8
? 10 1 5
? 10 7 11
? 10 5 11
? 10 1 11
?...

result:

ok OK, 26566 queries, 23 point in hull

Test #16:

score: 0
Accepted
time: 118ms
memory: 3456kb

input:

5000
-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:

? 1 2 3
? 1 3 4
? 1 2 4
? 3 2 4
? 4 1 2
? 4 3 1
? 4 1 5
? 4 3 5
? 1 3 5
? 5 4 3
? 5 1 2
? 5 4 6
? 5 2 6
? 4 2 6
? 6 1 2
? 6 4 3
? 6 5 7
? 6 3 7
? 6 4 7
? 7 2 6
? 7 1 2
? 7 4 3
? 7 5 8
? 7 2 8
? 8 1 2
? 8 5 1
? 8 7 4
? 8 3 9
? 8 1 9
? 9 5 1
? 9 3 5
? 9 8 7
? 9 4 10
? 9 7 10
? 9 8 10
? 7 8 10
? 9 4 11...

result:

ok OK, 27290 queries, 19 point in hull

Test #17:

score: 0
Accepted
time: 147ms
memory: 3420kb

input:

5000
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:

? 1 2 3
? 1 2 4
? 1 3 4
? 4 2 1
? 4 3 2
? 4 2 5
? 4 3 5
? 5 1 4
? 5 3 2
? 5 1 6
? 5 4 6
? 6 1 4
? 6 5 3
? 6 3 2
? 6 1 7
? 6 2 7
? 1 2 7
? 7 3 2
? 7 6 3
? 7 1 4
? 7 6 8
? 7 3 8
? 8 6 3
? 8 7 1
? 8 4 9
? 8 1 9
? 8 7 9
? 9 3 8
? 9 7 1
? 9 6 10
? 9 8 10
? 9 3 10
? 3 6 10
? 9 6 11
? 9 1 11
? 9 4 11
? 4 1...

result:

ok OK, 27252 queries, 25 point in hull

Test #18:

score: 0
Accepted
time: 123ms
memory: 3388kb

input:

5000
-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:

? 1 2 3
? 1 3 4
? 1 2 4
? 3 2 4
? 4 1 2
? 4 3 1
? 4 1 5
? 4 3 5
? 5 2 4
? 5 1 2
? 5 3 1
? 5 1 6
? 5 3 6
? 6 2 5
? 6 3 1
? 6 1 2
? 6 2 7
? 6 5 7
? 5 2 7
? 6 2 8
? 6 5 8
? 5 2 8
? 8 1 2
? 8 5 6
? 8 1 9
? 8 6 9
? 8 5 9
? 6 5 9
? 9 8 5
? 9 6 1
? 9 2 10
? 9 1 10
? 9 6 10
? 1 6 10
? 10 9 6
? 10 1 2
? 10 2...

result:

ok OK, 27362 queries, 24 point in hull

Test #19:

score: 0
Accepted
time: 111ms
memory: 3488kb

input:

5000
-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:

? 1 2 3
? 1 3 4
? 1 2 4
? 4 3 1
? 4 2 3
? 4 3 5
? 4 1 5
? 5 3 1
? 5 4 2
? 5 2 3
? 5 3 6
? 5 1 6
? 1 3 6
? 6 2 3
? 6 1 5
? 6 2 7
? 6 3 7
? 7 2 3
? 7 5 2
? 7 6 1
? 7 1 5
? 7 5 8
? 7 2 8
? 8 5 2
? 8 7 1
? 8 5 9
? 8 1 9
? 8 7 9
? 9 2 8
? 9 7 1
? 9 5 10
? 9 1 10
? 9 7 10
? 1 7 10
? 10 9 7
? 10 1 5
? 10 8...

result:

ok OK, 26960 queries, 23 point in hull

Test #20:

score: 0
Accepted
time: 125ms
memory: 3496kb

input:

5000
-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:

? 1 2 3
? 1 3 4
? 4 2 3
? 4 2 5
? 4 1 5
? 5 2 4
? 5 1 2
? 5 2 6
? 5 1 6
? 6 4 5
? 6 1 2
? 6 4 7
? 6 2 7
? 4 2 7
? 7 1 2
? 7 4 5
? 7 5 6
? 7 1 8
? 7 2 8
? 8 1 2
? 8 6 1
? 8 7 5
? 8 6 9
? 8 5 9
? 8 7 9
? 5 7 9
? 9 8 7
? 9 5 6
? 9 1 10
? 9 7 10
? 10 8 7
? 10 1 8
? 10 9 5
? 10 6 11
? 10 8 11
? 10 1 11
?...

result:

ok OK, 25160 queries, 19 point in hull

Test #21:

score: 0
Accepted
time: 89ms
memory: 3492kb

input:

5000
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:

? 1 2 3
? 1 2 4
? 1 3 4
? 2 3 4
? 4 1 3
? 4 2 1
? 4 1 5
? 4 2 5
? 5 3 4
? 5 2 1
? 5 3 6
? 5 4 6
? 4 3 6
? 6 1 3
? 6 4 5
? 6 2 7
? 6 3 7
? 7 1 3
? 7 2 1
? 7 6 4
? 7 5 8
? 7 1 8
? 8 2 1
? 8 5 2
? 8 7 6
? 8 6 4
? 8 5 9
? 8 4 9
? 8 6 9
? 4 6 9
? 9 8 6
? 9 4 5
? 9 2 10
? 9 6 10
? 9 8 10
? 6 8 10
? 10 2 8...

result:

ok OK, 25847 queries, 20 point in hull

Test #22:

score: 0
Accepted
time: 87ms
memory: 3504kb

input:

5000
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:

? 1 2 3
? 1 2 4
? 1 3 4
? 4 2 1
? 4 3 2
? 4 2 5
? 4 3 5
? 2 3 5
? 4 2 6
? 4 1 6
? 1 2 6
? 4 2 7
? 4 3 7
? 2 3 7
? 7 4 3
? 7 2 1
? 7 4 8
? 7 1 8
? 7 2 8
? 1 2 8
? 7 4 9
? 7 1 9
? 7 2 9
? 9 3 7
? 9 2 1
? 9 4 10
? 9 1 10
? 9 2 10
? 10 7 9
? 10 2 1
? 10 1 4
? 10 3 11
? 10 9 11
? 11 7 9
? 11 10 1
? 11 3 ...

result:

ok OK, 26964 queries, 24 point in hull

Test #23:

score: 0
Accepted
time: 77ms
memory: 3356kb

input:

5000
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:

? 1 2 3
? 1 2 4
? 1 3 4
? 2 3 4
? 1 2 5
? 5 3 2
? 5 1 3
? 5 3 6
? 5 2 6
? 6 3 2
? 6 5 1
? 6 1 3
? 6 3 7
? 6 1 7
? 3 1 7
? 7 6 1
? 7 3 2
? 7 6 8
? 7 1 8
? 8 6 1
? 8 2 6
? 8 7 3
? 8 2 9
? 8 3 9
? 2 3 9
? 9 7 3
? 9 8 7
? 9 2 6
? 9 8 10
? 9 6 10
? 8 6 10
? 9 8 11
? 9 6 11
? 8 6 11
? 11 2 6
? 11 8 7
? 11...

result:

ok OK, 26905 queries, 21 point in hull