QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#500830#8056. Travel 2CryingAC ✓130ms3992kbC++141.3kb2024-08-01 21:18:102024-08-01 21:18:11

Judging History

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

  • [2024-08-01 21:18:11]
  • 评测
  • 测评结果:AC
  • 用时:130ms
  • 内存:3992kb
  • [2024-08-01 21:18:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3010;

int T,n,fa[MAXN],tag[MAXN],deg[MAXN];

vector<int> e[MAXN];

void solve(){
    for(int i=1;i<=2500;i++){
        fa[i] = tag[i] = 0; 
        e[i].clear();
    }
    int pu = -1,pd = -1; n = 0;
    for(int u,d;;){
        auto walk = [&](int pos){
            cout<<"> "<<pos+1<<endl;
            pu = u,pd = pos;
        };  
        cin>>u>>d; n = max(n,u);
        e[u].resize(d,-1); deg[u] = d;
        if(pu != -1)e[pu][pd] = u;
        int pos = -1; for(int j=0;j<deg[u];j++)if(e[u][j]==-1){pos=j;break;}
        if(pos != -1){ 
            walk(pos);
            continue;
        }
        tag[u] = 1; 
        for(int j=0;j<deg[u];j++)if(!tag[e[u][j]]){pos=j;break;}
        if(pos != -1){
            fa[e[u][pos]] = u; 
            walk(pos);
            continue;
        }
        for(int j=0;j<deg[u];j++)if(e[u][j] == fa[u]){pos=j;break;}
        if(pos != -1){
            walk(pos);
            continue;
        }
        break;
    }
    cout<<"! ";
    for(int i=1;i<=n;i++)for(int j=0;j<deg[i];j++)if(i < e[i][j])cout<<i<<" "<<e[i][j]<<" "; cout<<endl;
    string str; cin>>str;
}

int main(){
    cin>>T;
    while(T--)solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3696kb

input:

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

output:

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

result:

ok correct! (2 test cases)

Test #2:

score: 0
Accepted
time: 115ms
memory: 3704kb

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

output:

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

result:

ok correct! (1000 test cases)

Test #3:

score: 0
Accepted
time: 117ms
memory: 3828kb

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
2 8
17 10
2 8
3 7
20 6
3 7
11 8
3 7
4 8
3 7
2 8
14 9
19 7
14 9
17 10
6 7
5 7
7 11
5 7
6 7
17 10
14 9
6 7
11...

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
> 1
> 2
> 2
> 3
> 2
> 2
> 3
> 2
> 4
> 2
> 5
> 4
> 2
> 2
> 3
> 3
> 2
> 2
> 2
> 3
> 3
> 4
> 4
> 4
> 3
> 2
> 4
> 2
> 2
> 3
> 5
> 3
> 2
> 4
> ...

result:

ok correct! (500 test cases)

Test #4:

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

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! (100 test cases)

Test #5:

score: 0
Accepted
time: 117ms
memory: 3784kb

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! (10 test cases)

Test #6:

score: 0
Accepted
time: 116ms
memory: 3692kb

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! (4 test cases)

Test #7:

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

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! (4 test cases)

Test #8:

score: 0
Accepted
time: 64ms
memory: 3992kb

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! (4 test cases)

Test #9:

score: 0
Accepted
time: 86ms
memory: 3984kb

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! (4 test cases)

Extra Test:

score: 0
Extra Test Passed