QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#553311	#9241. Sphinx	fansizhe	50	529ms	4860kb	C++20	3.4kb	2024-09-08 11:49:58	2024-09-08 11:49:59

Judging History

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

[2024-09-08 11:49:59]
评测

测评结果：50
用时：529ms
内存：4860kb

查看

[2024-09-08 11:49:58]
提交

answer

#include<bits/stdc++.h>
#include"sphinx.h"
using namespace std;
namespace{
    int n,m;
    int mat[255][255];
}
namespace Subtask0{
    int vis[255];
    int fa[255];
    int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
    int ask(vector<int> vec){
        for(int i=0;i<n;i++)if(vec[i]<0)vec[i]=get(i);
        int res=0;
        for(int i=0;i<n;i++)vis[i]=0;
        for(int i=0;i<n;i++)if(!vis[i]){
            res++;
            queue<int> que;
            que.push(i);vis[i]=1;
            while(!que.empty()){
                int x=que.front();que.pop();
                for(int y=0;y<n;y++)if(mat[x][y]&&!vis[y]&&vec[x]==vec[y])que.push(y),vis[y]=1;
            }
        }
        return res;
    }
    vector<int> solve(){
        for(int i=0;i<n;i++)fa[i]=i;
        for(int i=0;i<n;i++){
            vector<int> edge;
            for(int j=0;j<i;j++)if(mat[j][i])edge.push_back(j);
            vector<int> vec;
            for(int j=0;j<n;j++)vec.push_back(n);
            for(int j:edge)vec[j]=-1;
            vec[i]=-1;
            int val=perform_experiment(vec);
            vec[i]=i;
            while(!edge.empty()&&ask(vec)!=val){
                int l=0,r=edge.size()-1;
                while(l<r){
                    int mid=l+r>>1;
                    for(int j=0;j<l;j++)vec[edge[j]]=n;
                    for(int j=l;j<=mid;j++)vec[edge[j]]=-1;
                    for(int j=mid+1;j<edge.size();j++)vec[edge[j]]=n;
                    vec[i]=-1;
                    int val=perform_experiment(vec);
                    vec[i]=i;
                    if(ask(vec)!=val)r=mid;
                    else l=mid+1;
                }
                fa[get(i)]=get(edge[l]);
                vector<int> vv;
                for(int j=0;j<l;j++)vec[edge[j]]=n;
                for(int j=l;j<edge.size();j++)
                    if(get(edge[j])!=get(i))vec[edge[j]]=-1,vv.push_back(edge[j]);
                    else vec[edge[j]]=n;
                swap(edge,vv);
                vec[i]=-1;
                val=perform_experiment(vec);
                vec[i]=i;
            }
        }
        vector<int> res;
        for(int i=0;i<n;i++)res.push_back(get(i));
        return res;
    }
}
namespace Subtask1{
    bool check(){
        if(m>=n)return 0;
        for(int i=1;i<n;i++)if(!mat[i-1][i])return 0;
        return 1;
    }
    vector<int> solve(){
        vector<int> res;
        res.push_back(0);
        for(int i=1;i<n;i++){
            vector<int> vec;
            for(int j=0;j<i-1;j++)vec.push_back(n);
            vec.push_back(-1);
            vec.push_back(-1);
            for(int j=i+1;j<n;j++)vec.push_back(n);
            if(perform_experiment(vec)==(i>1)+1+(i<n-1))res.push_back(res.back());
            else res.push_back(res.back()^1);
        }
        return res;
    }
}
vector<int> find_colours(int _N,vector<int> _X,vector<int> _Y){
    n=_N,m=_X.size();
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)mat[i][j]=0;
    for(int i=0;i<m;i++)mat[_X[i]][_Y[i]]=mat[_Y[i]][_X[i]]=1;
    // if(n<=50){
    //     vector<int> res;
    //     for(int i=0;i<n;i++)
    //         for(int j=0;j<n;j++){
    //             vector<int> vec;
    //             for(int k=0;k<n;k++)if(k==i)vec.push_back(-1);else vec.push_back(j);
    //             if(perform_experiment(vec)==1){res.push_back(j);break;}
    //         }
    //     return res;
    // }else 
    return Subtask0::solve();
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1.5

Acceptable Answer

Test #1:

score: 3

Accepted

time: 1ms

memory: 3740kb

input:

output:

result:

ok #experiments: 3

Test #2:

score: 3

Accepted

time: 0ms

memory: 3808kb

input:

output:

result:

ok #experiments: 2

Test #3:

score: 1.5

Acceptable Answer

time: 0ms

memory: 3820kb

input:

output:

result:

points 0.50 points  0.5

Test #4:

score: 1.5

Acceptable Answer

time: 1ms

memory: 4120kb

input:

output:

result:

points 0.50 points  0.5

Subtask #2:

score: 3.5

Acceptable Answer

Dependency #1:

50%

Acceptable Answer

Test #5:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3808kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

points 0.50 points  0.5

Test #6:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3804kb

input:

output:

result:

points 0.50 points  0.5

Test #7:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3924kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

points 0.50 points  0.5

Test #8:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3892kb

input:

output:

result:

points 0.50 points  0.5

Test #9:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3940kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

points 0.50 points  0.5

Test #10:

score: 3.5

Acceptable Answer

time: 1ms

memory: 4124kb

input:

output:

result:

points 0.50 points  0.5

Test #11:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3924kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

points 0.50 points  0.5

Test #12:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3856kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

points 0.50 points  0.5

Test #13:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3844kb

input:

output:

result:

points 0.50 points  0.5

Test #14:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3864kb

input:

output:

result:

points 0.50 points  0.5

Test #15:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3948kb

input:

output:

result:

points 0.50 points  0.5

Test #16:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3904kb

input:

output:

result:

points 0.50 points  0.5

Test #17:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3828kb

input:

output:

result:

points 0.50 points  0.5

Test #18:

score: 3.5

Acceptable Answer

time: 0ms

memory: 4180kb

input:

output:

result:

points 0.50 points  0.5

Test #19:

score: 3.5

Acceptable Answer

time: 0ms

memory: 4140kb

input:

output:

result:

points 0.50 points  0.5

Test #20:

score: 3.5

Acceptable Answer

time: 4ms

memory: 3944kb

input:

output:

result:

points 0.50 points  0.5

Test #21:

score: 3.5

Acceptable Answer

time: 3ms

memory: 3832kb

input:

output:

result:

points 0.50 points  0.5

Test #22:

score: 3.5

Acceptable Answer

time: 3ms

memory: 4176kb

input:

output:

result:

points 0.50 points  0.5

Test #23:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3880kb

input:

output:

result:

points 0.50 points  0.5

Test #24:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3884kb

input:

output:

result:

points 0.50 points  0.5

Test #25:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3816kb

input:

output:

result:

points 0.50 points  0.5

Test #26:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3932kb

input:

output:

result:

points 0.50 points  0.5

Test #27:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3860kb

input:

1978433568
50
49
10
15
15
46
15
29
4
29
14
29
10
35
10
49
15
18
8
10
19
29
0
10
8
32
8
38
35
44
29
41
30
32
27
38
29
31
15
28
9
14
7
32
21
29
1
19
19
23
18
33
6
27
4
40
27
34
31
47
4
17
11
21
3
41
22
32
39
41
20
46
14
26
27
37
16
17
27
42
4
36
12
17
7
25
8
43
9
13
44
48
2
15
2
45
5
38
17
24
19784335...

output:

result:

points 0.50 points  0.5

Test #28:

score: 3.5

Acceptable Answer

time: 3ms

memory: 4132kb

input:

output:

result:

points 0.50 points  0.5

Test #29:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3904kb

input:

output:

result:

points 0.50 points  0.5

Test #30:

score: 3.5

Acceptable Answer

time: 5ms

memory: 4168kb

input:

output:

result:

points 0.50 points  0.5

Test #31:

score: 3.5

Acceptable Answer

time: 3ms

memory: 3884kb

input:

output:

result:

points 0.50 points  0.5

Test #32:

score: 3.5

Acceptable Answer

time: 3ms

memory: 3836kb

input:

output:

result:

points 0.50 points  0.5

Test #33:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3876kb

input:

output:

result:

points 0.50 points  0.5

Subtask #3:

score: 16.5

Acceptable Answer

Test #34:

score: 16.5

Acceptable Answer

time: 20ms

memory: 4064kb

input:

output:

result:

points 0.50 points  0.5

Test #35:

score: 16.5

Acceptable Answer

time: 10ms

memory: 4076kb

input:

output:

result:

points 0.50 points  0.5

Test #36:

score: 16.5

Acceptable Answer

time: 21ms

memory: 4076kb

input:

output:

result:

points 0.50 points  0.5

Test #37:

score: 16.5

Acceptable Answer

time: 19ms

memory: 4016kb

input:

output:

result:

points 0.50 points  0.5

Test #38:

score: 16.5

Acceptable Answer

time: 18ms

memory: 4148kb

input:

output:

result:

points 0.50 points  0.5

Test #39:

score: 16.5

Acceptable Answer

time: 14ms

memory: 4360kb

input:

output:

result:

points 0.50 points  0.5

Test #40:

score: 16.5

Acceptable Answer

time: 8ms

memory: 4020kb

input:

output:

result:

points 0.50 points  0.5

Test #41:

score: 16.5

Acceptable Answer

time: 16ms

memory: 4020kb

input:

output:

result:

points 0.50 points  0.5

Test #42:

score: 16.5

Acceptable Answer

time: 16ms

memory: 4068kb

input:

output:

result:

points 0.50 points  0.5

Subtask #4:

score: 10.5

Acceptable Answer

Test #43:

score: 10.5

Acceptable Answer

time: 165ms

memory: 4860kb

input:

output:

result:

points 0.50 points  0.5

Test #44:

score: 10.5

Acceptable Answer

time: 161ms

memory: 4556kb

input:

output:

result:

points 0.50 points  0.5

Test #45:

score: 10.5

Acceptable Answer

time: 178ms

memory: 4552kb

input:

output:

result:

points 0.50 points  0.5

Test #46:

score: 10.5

Acceptable Answer

time: 165ms

memory: 4852kb

input:

output:

result:

points 0.50 points  0.5

Test #47:

score: 10.5

Acceptable Answer

time: 136ms

memory: 4564kb

input:

output:

result:

points 0.50 points  0.5

Test #48:

score: 10.5

Acceptable Answer

time: 106ms

memory: 4856kb

input:

output:

result:

points 0.50 points  0.5

Test #49:

score: 10.5

Acceptable Answer

time: 84ms

memory: 4556kb

input:

output:

result:

points 0.50 points  0.5

Test #50:

score: 10.5

Acceptable Answer

time: 165ms

memory: 4552kb

input:

output:

result:

points 0.50 points  0.5

Test #51:

score: 10.5

Acceptable Answer

time: 20ms

memory: 4508kb

input:

output:

result:

points 0.50 points  0.5

Subtask #5:

score: 18

Acceptable Answer

Dependency #1:

50%

Acceptable Answer

Dependency #2:

50%

Acceptable Answer

Dependency #3:

50%

Acceptable Answer

Dependency #4:

50%

Acceptable Answer

Test #52:

score: 18

Acceptable Answer

time: 54ms

memory: 4384kb

input:

output:

result:

points 0.50 points  0.5

Test #53:

score: 18

Acceptable Answer

time: 67ms

memory: 4136kb

input:

output:

result:

points 0.50 points  0.5

Test #54:

score: 18

Acceptable Answer

time: 66ms

memory: 4348kb

input:

output:

result:

points 0.50 points  0.5

Test #55:

score: 18

Acceptable Answer

time: 100ms

memory: 4140kb

input:

output:

result:

points 0.50 points  0.5

Test #56:

score: 18

Acceptable Answer

time: 86ms

memory: 4280kb

input:

output:

result:

points 0.50 points  0.5

Test #57:

score: 18

Acceptable Answer

time: 76ms

memory: 4268kb

input:

output:

result:

points 0.50 points  0.5

Test #58:

score: 18

Acceptable Answer

time: 76ms

memory: 4296kb

input:

output:

result:

points 0.50 points  0.5

Test #59:

score: 18

Acceptable Answer

time: 82ms

memory: 4560kb

input:

output:

result:

points 0.50 points  0.5

Test #60:

score: 18

Acceptable Answer

time: 16ms

memory: 4076kb

input:

output:

result:

points 0.50 points  0.5

Test #61:

score: 18

Acceptable Answer

time: 6ms

memory: 4040kb

input:

output:

result:

points 0.50 points  0.5

Test #62:

score: 18

Acceptable Answer

time: 12ms

memory: 4064kb

input:

output:

result:

points 0.50 points  0.5

Test #63:

score: 18

Acceptable Answer

time: 121ms

memory: 4180kb

input:

output:

result:

points 0.50 points  0.5

Test #64:

score: 18

Acceptable Answer

time: 131ms

memory: 4404kb

input:

output:

result:

points 0.50 points  0.5

Test #65:

score: 18

Acceptable Answer

time: 132ms

memory: 4404kb

input:

output:

result:

points 0.50 points  0.5

Test #66:

score: 18

Acceptable Answer

time: 116ms

memory: 4176kb

input:

output:

result:

points 0.50 points  0.5

Test #67:

score: 18

Acceptable Answer

time: 170ms

memory: 4136kb

input:

output:

result:

points 0.50 points  0.5

Test #68:

score: 18

Acceptable Answer

time: 156ms

memory: 4120kb

input:

output:

result:

points 0.50 points  0.5

Test #69:

score: 18

Acceptable Answer

time: 143ms

memory: 4172kb

input:

output:

result:

points 0.50 points  0.5

Test #70:

score: 18

Acceptable Answer

time: 180ms

memory: 4156kb

input:

output:

result:

points 0.50 points  0.5

Test #71:

score: 18

Acceptable Answer

time: 29ms

memory: 4380kb

input:

output:

result:

points 0.50 points  0.5

Test #72:

score: 18

Acceptable Answer

time: 77ms

memory: 4088kb

input:

output:

result:

points 0.50 points  0.5

Test #73:

score: 18

Acceptable Answer

time: 90ms

memory: 4160kb

input:

output:

result:

points 0.50 points  0.5

Test #74:

score: 18

Acceptable Answer

time: 143ms

memory: 4124kb

input:

output:

result:

points 0.50 points  0.5

Test #75:

score: 18

Acceptable Answer

time: 146ms

memory: 4172kb

input:

output:

result:

points 0.50 points  0.5

Test #76:

score: 18

Acceptable Answer

time: 170ms

memory: 4088kb

input:

output:

result:

points 0.50 points  0.5

Test #77:

score: 18

Acceptable Answer

time: 177ms

memory: 4132kb

input:

output:

result:

points 0.50 points  0.5

Test #78:

score: 18

Acceptable Answer

time: 230ms

memory: 4416kb

input:

output:

result:

points 0.50 points  0.5

Test #79:

score: 18

Acceptable Answer

time: 197ms

memory: 4160kb

input:

output:

result:

points 0.50 points  0.5

Test #80:

score: 18

Acceptable Answer

time: 206ms

memory: 4124kb

input:

output:

result:

points 0.50 points  0.5

Test #81:

score: 18

Acceptable Answer

time: 70ms

memory: 4448kb

input:

output:

result:

points 0.50 points  0.5

Test #82:

score: 18

Acceptable Answer

time: 529ms

memory: 4684kb

input:

output:

result:

points 0.50 points  0.5

Test #83:

score: 18

Acceptable Answer

time: 171ms

memory: 4496kb

input:

output:

result:

points 0.50 points  0.5

Test #84:

score: 18

Acceptable Answer

time: 324ms

memory: 4096kb

input:

output:

result:

points 0.50 points  0.5

Test #85:

score: 18

Acceptable Answer

time: 74ms

memory: 4296kb

input:

output:

result:

points 0.50 points  0.5