QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#741369#8056. Travel 2dezexTL 149ms4112kbC++202.1kb2024-11-13 14:13:082024-11-13 14:13:08

Judging History

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

  • [2024-11-13 14:13:08]
  • 评测
  • 测评结果:TL
  • 用时:149ms
  • 内存:4112kb
  • [2024-11-13 14:13:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=2500+10;
set<int> ro[N];
vector<int> o[N];
map<int,int> ou_ord[N];

int vis[N];
set<pair<int,int>> ans;
int cur,dcur;
int n;

void newNode(int x,int dx)
{
    n=max(n,x);
    vis[x]=1;
    ro[x].clear();
    for(int i=1;i<=dx;i++)  
        ro[x].insert(i);
    // printf("x=%d dx=%d\n",x,dx);
    o[x].resize(dx + 1);
    fill(o[x].begin(),o[x].end(),0);
    ou_ord[x].clear();
}


void step(int ord)
{
    printf("> %d\n",ord);
    fflush(stdout);

    int ocur = cur;
    scanf("%d %d",&cur,&dcur);
    // printf("why cur=%d size=%u ord=%d\n",ocur,o[ocur].size(),ord);

    o[ocur][ord] = cur;
    ou_ord[ocur][cur] = ord;
    // v=cur;
    // printf("hhhhh!\n");
    if(vis[cur]==0)
        newNode(cur,dcur);
}

void euler(int tgt)
{
    while(true)
    {
        assert(!ro[cur].empty());
        int ord = *ro[cur].begin();
        ro[cur].erase(ord);

        step(ord);

        if(cur == tgt)
            break;
    };
}


void dfs(int u)
{
    while(!ro[u].empty())
    {
        int ord = *ro[u].begin();
        ro[u].erase(ord);

        step(ord);

        euler(u);
    }
        
    //cur == u
    for(int i=1;i<o[u].size();i++)
        if(!ro[o[u][i]].empty())
        {
            step(i);
            dfs(o[u][i]);
            int ord = ou_ord[cur][u];
            step(ord);
        };
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        n=0;
        memset(vis,0,sizeof(vis));
        scanf("%d %d",&cur,&dcur);
        newNode(cur,dcur);
        dfs(cur);
        ans.clear();
        for(int i=1;i<=n;i++)
            for(auto j:o[i])
            {
                if(j==0)
                    continue;
                if(i>j) 
                    ans.insert(make_pair(j,i));
                else
                    ans.insert(make_pair(i,j));
            };
        printf("! ");
        for(auto [u,v]:ans)
            printf("%d %d ",u,v);
        printf("\n");
        fflush(stdout);
        char s[100];
        scanf("%s",s);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok correct! (2 test cases)

Test #2:

score: 0
Accepted
time: 149ms
memory: 4008kb

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: -100
Time Limit Exceeded

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: