QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#560459	#9241. Sphinx	chenxinyang2006^#	64	376ms	4836kb	C++20	3.4kb	2024-09-12 15:49:40	2024-09-12 15:49:40

Judging History

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

[2024-09-12 15:49:40]
评测

测评结果：64
用时：376ms
内存：4836kb

查看

[2024-09-12 15:49:40]
提交

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],col[255],vis[255],cur[255],bas[255],ord[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(vector <int> &C){
    rep(u,1,n) fa[u] = u;
    rep(u,1,n){
        for(int v:G[u]){
            if(C[u - 1] == C[v - 1]) 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("ret=%d\n",ret);
    return ret;
}

bool cmp(int x,int y){
    return cur[x] < cur[y];
}

int check(vector <int> &C){
    int res1 = test(C),res2 = query(C);
//    for(int c:C) printf("%d ",c);
//    printf("\n%d %d\n",res1,res2);
    return res1 == res2;
}
int sz;
pii idx[255];
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]);
    }
    rep(u,1,n) cur[u] = 0;
    vector <int> ans(n),C(n),CC(n);
    while(1){
        rep(u,1,n){
            ord[u] = u;
            vis[u] = 0;
        }
        sort(ord + 1,ord + n + 1,cmp);
        if(cur[ord[1]] >= n) break;

        rep(u,1,n) bas[u] = cur[u];
        sz = 0;
        rep(_i,1,n){
            int u = ord[_i];
            if(vis[u]) continue;
            int fail = 0;
            for(int v:G[u]) fail += vis[v];
            if(fail) continue;
            vis[u] = 1;
            col[u] = -1;
            for(int v:G[u]){
                if(vis[v]) continue;
                vis[v] = 1;
                col[v] = cur[u]++;
                idx[++sz] = mkp(u,v);
//                printf("%d:(%d,%d)\n",sz,u,v);
                chkmin(cur[u],n);
            }
        }
//        rep(u,1,n) printf("%d ",col[u]);
//        printf("\n");
        rep(u,1,n){
            if(!vis[u]) col[u] = n;
            C[u - 1] = col[u];
        }
        if(check(C)) continue;

        int pl = 1,pr = sz,mid;
        while(pl != pr){
            mid = (pl + pr) >> 1;
            CC = C;
            rep(i,1,pl - 1) CC[idx[i].second - 1] = n;
            rep(i,mid+1,sz) CC[idx[i].second - 1] = n;
            if(check(CC)) pl = mid + 1;
            else pr = mid;
        }
        ans[idx[pl].first - 1] = col[idx[pl].second];
        rep(u,1,n) cur[u] = bas[u];
        cur[idx[pl].first] = n;
    }
    return ans;
}
/*
g++ sphinx3.cpp grader.cpp -o grader3.exe -Wall -Wshadow -O2 -std=c++14
*/

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 1ms

memory: 3816kb

input:

output:

result:

ok #experiments: 2

Test #2:

score: 3

Accepted

time: 1ms

memory: 3740kb

input:

output:

result:

ok #experiments: 3

Test #3:

score: 3

Accepted

time: 1ms

memory: 3784kb

input:

output:

result:

ok #experiments: 3

Test #4:

score: 3

Accepted

time: 0ms

memory: 3788kb

input:

output:

result:

ok #experiments: 4

Subtask #2:

score: 7

Accepted

Dependency #1:

100%

Accepted

Test #5:

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: 348

Test #6:

score: 7

Accepted

time: 0ms

memory: 3792kb

input:

output:

result:

ok #experiments: 389

Test #7:

score: 7

Accepted

time: 3ms

memory: 3796kb

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: 385

Test #8:

score: 7

Accepted

time: 0ms

memory: 3736kb

input:

output:

result:

ok #experiments: 357

Test #9:

score: 7

Accepted

time: 2ms

memory: 3788kb

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: 351

Test #10:

score: 7

Accepted

time: 3ms

memory: 3784kb

input:

output:

result:

ok #experiments: 363

Test #11:

score: 7

Accepted

time: 3ms

memory: 3884kb

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: 357

Test #12:

score: 7

Accepted

time: 3ms

memory: 3744kb

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: 356

Test #13:

score: 7

Accepted

time: 4ms

memory: 3704kb

input:

output:

result:

ok #experiments: 263

Test #14:

score: 7

Accepted

time: 0ms

memory: 3792kb

input:

output:

result:

ok #experiments: 277

Test #15:

score: 7

Accepted

time: 4ms

memory: 3828kb

input:

output:

result:

ok #experiments: 257

Test #16:

score: 7

Accepted

time: 0ms

memory: 3800kb

input:

output:

result:

ok #experiments: 279

Test #17:

score: 7

Accepted

time: 5ms

memory: 3816kb

input:

output:

result:

ok #experiments: 350

Test #18:

score: 7

Accepted

time: 2ms

memory: 4112kb

input:

output:

result:

ok #experiments: 322

Test #19:

score: 7

Accepted

time: 5ms

memory: 4124kb

input:

output:

result:

ok #experiments: 322

Test #20:

score: 7

Accepted

time: 5ms

memory: 4076kb

input:

output:

result:

ok #experiments: 342

Test #21:

score: 7

Accepted

time: 4ms

memory: 3828kb

input:

output:

result:

ok #experiments: 343

Test #22:

score: 7

Accepted

time: 5ms

memory: 3824kb

input:

output:

result:

ok #experiments: 326

Test #23:

score: 7

Accepted

time: 2ms

memory: 4084kb

input:

output:

result:

ok #experiments: 333

Test #24:

score: 7

Accepted

time: 5ms

memory: 4128kb

input:

output:

result:

ok #experiments: 336

Test #25:

score: 7

Accepted

time: 3ms

memory: 3864kb

input:

output:

result:

ok #experiments: 403

Test #26:

score: 7

Accepted

time: 2ms

memory: 3880kb

input:

output:

result:

ok #experiments: 366

Test #27:

score: 7

Accepted

time: 0ms

memory: 4068kb

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: 402

Test #28:

score: 7

Accepted

time: 4ms

memory: 3888kb

input:

output:

result:

ok #experiments: 320

Test #29:

score: 7

Accepted

time: 3ms

memory: 3808kb

input:

output:

result:

ok #experiments: 302

Test #30:

score: 7

Accepted

time: 0ms

memory: 4120kb

input:

output:

result:

ok #experiments: 332

Test #31:

score: 7

Accepted

time: 0ms

memory: 3820kb

input:

output:

result:

ok #experiments: 349

Test #32:

score: 7

Accepted

time: 4ms

memory: 3800kb

input:

output:

result:

ok #experiments: 326

Test #33:

score: 7

Accepted

time: 4ms

memory: 4040kb

input:

output:

result:

ok #experiments: 323

Subtask #3:

score: 33

Accepted

Test #34:

score: 33

Accepted

time: 31ms

memory: 3828kb

input:

output:

result:

ok #experiments: 2298

Test #35:

score: 33

Accepted

time: 40ms

memory: 3824kb

input:

output:

result:

ok #experiments: 2492

Test #36:

score: 33

Accepted

time: 43ms

memory: 3900kb

input:

output:

result:

ok #experiments: 2463

Test #37:

score: 33

Accepted

time: 48ms

memory: 3828kb

input:

output:

result:

ok #experiments: 2438

Test #38:

score: 33

Accepted

time: 47ms

memory: 3828kb

input:

output:

result:

ok #experiments: 2446

Test #39:

score: 33

Accepted

time: 44ms

memory: 3804kb

input:

output:

result:

ok #experiments: 2472

Test #40:

score: 33

Accepted

time: 51ms

memory: 4056kb

input:

output:

result:

ok #experiments: 2442

Test #41:

score: 33

Accepted

time: 41ms

memory: 3752kb

input:

output:

result:

ok #experiments: 2339

Test #42:

score: 33

Accepted

time: 55ms

memory: 3804kb

input:

output:

result:

ok #experiments: 2458

Subtask #4:

score: 21

Accepted

Test #43:

score: 21

Accepted

time: 341ms

memory: 4552kb

input:

output:

result:

ok #experiments: 2138

Test #44:

score: 21

Accepted

time: 354ms

memory: 4632kb

input:

output:

result:

ok #experiments: 2250

Test #45:

score: 21

Accepted

time: 359ms

memory: 4568kb

input:

output:

result:

ok #experiments: 2250

Test #46:

score: 21

Accepted

time: 376ms

memory: 4548kb

input:

output:

result:

ok #experiments: 2243

Test #47:

score: 21

Accepted

time: 369ms

memory: 4836kb

input:

output:

result:

ok #experiments: 2246

Test #48:

score: 21

Accepted

time: 364ms

memory: 4548kb

input:

output:

result:

ok #experiments: 2247

Test #49:

score: 21

Accepted

time: 364ms

memory: 4544kb

input:

output:

result:

ok #experiments: 2243

Test #50:

score: 21

Accepted

time: 364ms

memory: 4568kb

input:

output:

result:

ok #experiments: 2250

Test #51:

score: 21

Accepted

time: 359ms

memory: 4544kb

input:

output:

result:

ok #experiments: 2244

Subtask #5:

score: 0

Runtime Error

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Test #52:

score: 36

Accepted

time: 68ms

memory: 4140kb

input:

output:

result:

ok #experiments: 2384

Test #53:

score: 36

Accepted

time: 76ms

memory: 3888kb

input:

output:

result:

ok #experiments: 2280

Test #54:

score: 36

Accepted

time: 80ms

memory: 3896kb

input:

output:

result:

ok #experiments: 2331

Test #55:

score: 36

Accepted

time: 76ms

memory: 3912kb

input:

output:

result:

ok #experiments: 2269

Test #56:

score: 36

Accepted

time: 187ms

memory: 4392kb

input:

output:

result:

ok #experiments: 1948

Test #57:

score: 36

Accepted

time: 167ms

memory: 4156kb

input:

output:

result:

ok #experiments: 1841

Test #58:

score: 36

Accepted

time: 179ms

memory: 4156kb

input:

output:

result:

ok #experiments: 1849

Test #59:

score: 36

Accepted

time: 214ms

memory: 4392kb

input:

output:

result:

ok #experiments: 1978

Test #60:

score: 0

Runtime Error

input:

output: