QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#560264	#9241. Sphinx	chenxinyang2006^#	10	12ms	4112kb	C++20	2.1kb	2024-09-12 14:42:38	2024-09-12 14:42:39

Judging History

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

[2024-09-12 14:42:39]
评测

测评结果：10
用时：12ms
内存：4112kb

查看

[2024-09-12 14:42:38]
提交

answer

#include "sphinx.h"
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
  if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
  if(x > y) x = y;
}

inline int popcnt(int x){
  return __builtin_popcount(x);
}

inline int ctz(int x){
  return __builtin_ctz(x);
}
int n;
vector <int> G[255];
int fa[255];
int fnd(int u){
    if(fa[u] == u) return u;
    return fa[u] = fnd(fa[u]);
}
void mrg(int u,int v){
    u = fnd(u);v = fnd(v);
    if(u == v) return;
    fa[u] = v;
}

int test(int p,int q){
    rep(u,1,n) fa[u] = u;
    rep(u,1,n){
        if(u == p || u == q) continue;
        for(int v:G[u]){
            if(v == p || v == q) continue;
            mrg(u,v);
        }
    }
    int result = 0;
    rep(u,1,n) result += fa[u] == u;
    return result;
}

int query(vector <int> &C){
    assert(SZ(C) == n);
    int ret = perform_experiment(C);
//    for(int c:C) printf("%d ",c);
//    printf("\nret=%d\n",ret);
    return ret;
}

vector <int> find_colours(int N, vector<int> X,vector<int> Y) {
    n = N;
    rep(i,0,SZ(X) - 1){
        X[i]++;Y[i]++;
        G[X[i]].eb(Y[i]);
        G[Y[i]].eb(X[i]);
    }
    vector <int> C(n),ans(n);
    rep(u,1,n){
        int v = G[u][0],bas = test(u,v);
//        cerr << u << " " << v << " bas=" << bas << endl;
        rep(w,0,n - 1){
            C = vector <int>(n,n);
            C[u - 1] = -1;
            C[v - 1] = w;
            if(query(C) == bas - 1){
                ans[u - 1] = w;
                break;
            }
        }
    }
    return ans;
}
/*
g++ sphinx.cpp grader.cpp -o grader.exe -Wall -Wshadow -O2 -std=c++14
*/

源文件, 语言: C++20

详细

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 1ms

memory: 4036kb

input:

output:

result:

ok #experiments: 2

Test #2:

score: 3

Accepted

time: 0ms

memory: 3784kb

input:

output:

result:

ok #experiments: 3

Test #3:

score: 3

Accepted

time: 1ms

memory: 4080kb

input:

output:

result:

ok #experiments: 3

Test #4:

score: 3

Accepted

time: 0ms

memory: 3860kb

input:

output:

result:

ok #experiments: 4

Subtask #2:

score: 7

Accepted

Dependency #1:

100%

Accepted

Test #5:

score: 7

Accepted

time: 7ms

memory: 4064kb

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:

ok #experiments: 1250

Test #6:

score: 7

Accepted

time: 2ms

memory: 3780kb

input:

output:

result:

ok #experiments: 785

Test #7:

score: 7

Accepted

time: 9ms

memory: 3864kb

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:

ok #experiments: 1613

Test #8:

score: 7

Accepted

time: 9ms

memory: 3780kb

input:

output:

result:

ok #experiments: 1353

Test #9:

score: 7

Accepted

time: 0ms

memory: 3776kb

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:

ok #experiments: 1138

Test #10:

score: 7

Accepted

time: 8ms

memory: 3780kb

input:

output:

result:

ok #experiments: 978

Test #11:

score: 7

Accepted

time: 4ms

memory: 3780kb

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:

ok #experiments: 1278

Test #12:

score: 7

Accepted

time: 0ms

memory: 3804kb

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:

ok #experiments: 1275

Test #13:

score: 7

Accepted

time: 2ms

memory: 3816kb

input:

output:

result:

ok #experiments: 196

Test #14:

score: 7

Accepted

time: 2ms

memory: 3796kb

input:

output:

result:

ok #experiments: 150

Test #15:

score: 7

Accepted

time: 3ms

memory: 3796kb

input:

output:

result:

ok #experiments: 312

Test #16:

score: 7

Accepted

time: 2ms

memory: 3876kb

input:

output:

result:

ok #experiments: 650

Test #17:

score: 7

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok #experiments: 750

Test #18:

score: 7

Accepted

time: 0ms

memory: 3820kb

input:

output:

result:

ok #experiments: 920

Test #19:

score: 7

Accepted

time: 6ms

memory: 3844kb

input:

output:

result:

ok #experiments: 1361

Test #20:

score: 7

Accepted

time: 7ms

memory: 3820kb

input:

output:

result:

ok #experiments: 1109

Test #21:

score: 7

Accepted

time: 2ms

memory: 3840kb

input:

output:

result:

ok #experiments: 1506

Test #22:

score: 7

Accepted

time: 0ms

memory: 3820kb

input:

output:

result:

ok #experiments: 1280

Test #23:

score: 7

Accepted

time: 9ms

memory: 3816kb

input:

output:

result:

ok #experiments: 1376

Test #24:

score: 7

Accepted

time: 4ms

memory: 3844kb

input:

output:

result:

ok #experiments: 1275

Test #25:

score: 7

Accepted

time: 8ms

memory: 3800kb

input:

output:

result:

ok #experiments: 966

Test #26:

score: 7

Accepted

time: 6ms

memory: 3800kb

input:

output:

result:

ok #experiments: 1071

Test #27:

score: 7

Accepted

time: 11ms

memory: 3800kb

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:

ok #experiments: 1208

Test #28:

score: 7

Accepted

time: 0ms

memory: 3788kb

input:

output:

result:

ok #experiments: 1179

Test #29:

score: 7

Accepted

time: 1ms

memory: 3872kb

input:

output:

result:

ok #experiments: 1209

Test #30:

score: 7

Accepted

time: 6ms

memory: 4112kb

input:

output:

result:

ok #experiments: 1187

Test #31:

score: 7

Accepted

time: 3ms

memory: 4104kb

input:

output:

result:

ok #experiments: 1417

Test #32:

score: 7

Accepted

time: 4ms

memory: 3812kb

input:

output:

result:

ok #experiments: 1470

Test #33:

score: 7

Accepted

time: 12ms

memory: 4100kb

input:

output:

result:

ok #experiments: 1275

Subtask #3:

score: 0

Runtime Error

Test #34:

score: 0

Runtime Error

input:

output:

result:

Subtask #4:

score: 0

Runtime Error

Test #43:

score: 0

Runtime Error

input:

output:

result:

Subtask #5:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted