QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#330759#8056. Travel 2ucup-team1600#AC ✓218ms28580kbC++203.2kb2024-02-17 18:46:112024-02-17 18:46:11

Judging History

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

  • [2024-02-17 18:46:11]
  • 评测
  • 测评结果:AC
  • 用时:218ms
  • 内存:28580kb
  • [2024-02-17 18:46:11]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

mt19937 rng(4242);

const int max_n = 2505, inf = 1000111222;

int cv = 0;

vector<int> g[max_n];

int deg[max_n];

int done[max_n];

int edg_num[max_n][max_n];

pair<int, int> go(int i) {
    cout << "> " << i << endl;
    int x, dx;
    cin >> x >> dx;
    return {x, dx};
}

void solve() {
    cin >> cv; cv--;
    cin >> deg[cv];
    vector<int> ord;
    int mx_node = cv;
    while(true) {
        umax(mx_node, cv);
//        cout << cv << ' ' << done[cv] << ' ' << deg[cv] << '\n';
        if(done[cv] == deg[cv]) {
            if(ord.empty()) break;
            bool bruh = false;
            map<int, int> have;
            vector<int> to_go;
            for(int i = len(ord) - 1; i >= 0; i--) {
                if(have[ord[i]] > 0) {
                    while(to_go.back() != ord[i]) {
                        have[to_go.back()]--;
                        to_go.pop_back();
                    }
                } else {
                    have[ord[i]]++;
                    to_go.pb(ord[i]);
                }
                if(done[ord[i]] != deg[ord[i]]) break;
                if(i == 0) bruh = true;
            }
            if(bruh) break;
            for(auto& x : to_go) {
                auto to = go(edg_num[cv][x]);
                cv = to.fi - 1; deg[cv] = to.se;
            }
        } else {
            done[cv]++;
            auto to = go(done[cv]);
            ord.pb(cv);
            edg_num[cv][to.fi - 1] = done[cv];
            cv = to.fi - 1; deg[cv] = to.se;
        }
    }
    cout << "! ";
    for(int i = 0; i <= mx_node; i++) {
        done[i] = 0;
        deg[i] = -1;
        for (int j = i + 1; j <= mx_node; j++) {
            if (edg_num[i][j] != -1)
                cout << i + 1 << ' ' << j + 1 << ' ';
            edg_num[i][j] = -1;
        }
    }
    cout << endl;
    string s; cin >> s;
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for(int i = 0; i < max_n; i++)
        for(int j = 0; j < max_n; j++)
            edg_num[i][j] = -1;

    int t = 1;

    cin >> t;

    while (t--) solve();

}

/*
KIVI
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 28368kb

input:

2
1 1
2 1
1 1
Correct
1 3
2 2
1 3
3 1
1 3
4 2
1 3
4 2
2 2
4 2
Correct

output:

> 1
> 1
! 1 2 
> 1
> 1
> 2
> 1
> 3
> 1
> 3
> 2
> 2
! 1 2 1 3 1 4 2 4 

result:

ok correct

Test #2:

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

input:

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

output:

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

result:

ok correct

Test #3:

score: 0
Accepted
time: 94ms
memory: 28172kb

input:

500
1 19
2 8
1 19
3 7
1 19
4 8
1 19
5 7
1 19
6 7
1 19
7 11
1 19
8 4
1 19
9 7
1 19
10 9
1 19
11 8
1 19
12 7
1 19
13 4
1 19
14 9
1 19
15 8
1 19
16 7
1 19
17 10
1 19
18 7
1 19
19 7
1 19
20 6
1 19
20 6
3 7
20 6
15 8
20 6
9 7
4 8
3 7
11 8
3 7
4 8
12 7
4 8
7 11
5 7
7 11
16 7
13 4
16 7
11 8
8 4
11 8
16 7
7...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 19
> 2
> 2
> 3
> 2
> 4
> 2
> 2
> 3
> 2
> 4
> 3
> 2
> 4
> 2
> 2
> 3
> 2
> 2
> 3
> 3
> 2
> 4
> 4
> 4
> 5
> 5
> 6
> 3
> 2
> 2
> 3
> 2
> 2
>...

result:

ok correct

Test #4:

score: 0
Accepted
time: 142ms
memory: 28116kb

input:

100
1 99
2 5
1 99
3 5
1 99
4 10
1 99
5 3
1 99
6 9
1 99
7 6
1 99
8 8
1 99
9 9
1 99
10 5
1 99
11 4
1 99
12 7
1 99
13 6
1 99
14 8
1 99
15 7
1 99
16 7
1 99
17 7
1 99
18 6
1 99
19 10
1 99
20 4
1 99
21 4
1 99
22 5
1 99
23 6
1 99
24 10
1 99
25 4
1 99
26 10
1 99
27 7
1 99
28 6
1 99
29 11
1 99
30 5
1 99
31 7...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Test #5:

score: 0
Accepted
time: 218ms
memory: 28232kb

input:

10
1 999
2 8
1 999
3 9
1 999
4 8
1 999
5 7
1 999
6 7
1 999
7 4
1 999
8 4
1 999
9 13
1 999
10 11
1 999
11 7
1 999
12 7
1 999
13 5
1 999
14 5
1 999
15 8
1 999
16 9
1 999
17 5
1 999
18 5
1 999
19 8
1 999
20 4
1 999
21 8
1 999
22 8
1 999
23 6
1 999
24 8
1 999
25 2
1 999
26 9
1 999
27 5
1 999
28 6
1 999
...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Test #6:

score: 0
Accepted
time: 194ms
memory: 28356kb

input:

4
1 999
2 24
1 999
3 20
1 999
4 17
1 999
5 29
1 999
6 21
1 999
7 21
1 999
8 19
1 999
9 21
1 999
10 14
1 999
11 12
1 999
12 17
1 999
13 23
1 999
14 23
1 999
15 16
1 999
16 14
1 999
17 16
1 999
18 15
1 999
19 16
1 999
20 19
1 999
21 16
1 999
22 16
1 999
23 25
1 999
24 23
1 999
25 22
1 999
26 16
1 999
...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Test #7:

score: 0
Accepted
time: 93ms
memory: 28348kb

input:

4
1 199
2 106
1 199
3 95
1 199
4 102
1 199
5 103
1 199
6 103
1 199
7 110
1 199
8 109
1 199
9 104
1 199
10 98
1 199
11 85
1 199
12 94
1 199
13 86
1 199
14 105
1 199
15 102
1 199
16 96
1 199
17 97
1 199
18 94
1 199
19 112
1 199
20 108
1 199
21 116
1 199
22 109
1 199
23 104
1 199
24 96
1 199
25 92
1 19...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Test #8:

score: 0
Accepted
time: 80ms
memory: 28328kb

input:

4
1 140
2 140
1 140
3 140
1 140
4 140
1 140
5 140
1 140
6 140
1 140
7 140
1 140
8 140
1 140
9 140
1 140
10 140
1 140
11 140
1 140
12 140
1 140
13 140
1 140
14 140
1 140
15 140
1 140
16 140
1 140
17 140
1 140
18 140
1 140
19 140
1 140
20 140
1 140
21 140
1 140
22 140
1 140
23 140
1 140
24 140
1 140
2...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Test #9:

score: 0
Accepted
time: 73ms
memory: 28580kb

input:

4
1 2498
2 2
1 2498
3 2
1 2498
4 2
1 2498
5 2
1 2498
6 2
1 2498
7 2
1 2498
8 2
1 2498
9 2
1 2498
10 2
1 2498
11 2
1 2498
12 2
1 2498
13 2
1 2498
14 2
1 2498
15 2
1 2498
16 2
1 2498
17 2
1 2498
18 2
1 2498
19 2
1 2498
20 2
1 2498
21 2
1 2498
22 2
1 2498
23 2
1 2498
24 2
1 2498
25 2
1 2498
26 2
1 2498...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Extra Test:

score: 0
Extra Test Passed