QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#711206#9241. Sphinxivan_alexeev#22.5 50ms4832kbC++233.7kb2024-11-05 02:25:182024-11-05 02:25:18

Judging History

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

  • [2024-11-05 02:25:18]
  • 评测
  • 测评结果:22.5
  • 用时:50ms
  • 内存:4832kb
  • [2024-11-05 02:25:18]
  • 提交

answer

#include <bits/stdc++.h>
#include "sphinx.h"

using namespace std;

#ifdef lisie_bimbi
#else
#define endl '\n'
#endif
typedef long long ll;

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")

const ll inf = 1'000'000'000;


#ifdef lisie_bimbi
namespace {

const int CALLS_CNT_LIMIT = 2750;

int calls_cnt;

int N, M;
std::vector<int> C;
std::vector<int> X, Y;
std::vector<std::vector<int>> adj;

void quit(const char* message) {
    printf("%s\n", message);
    exit(0);
}

int count_components(const std::vector<int>& S) {
  int components_cnt = 0;
  std::vector<bool> vis(N, false);
  for (int i = 0; i < N; i++) {
      if (vis[i])
          continue;
      components_cnt++;

      std::queue<int> q;
      vis[i] = true;
      q.push(i);
      while (!q.empty()) {
          int cur = q.front();
          q.pop();
          for (int nxt : adj[cur])
              if (!vis[nxt] && S[nxt] == S[cur]) {
                  vis[nxt] = true;
                  q.push(nxt);
              }
      }
  }
  return components_cnt;
}

} // namespace

int perform_experiment(std::vector<int> E) {
    calls_cnt++;
    if (calls_cnt > CALLS_CNT_LIMIT)
        quit("Too many calls");
    if ((int)E.size() != N)
        quit("Invalid argument");
    for (int i = 0; i < N; i++)
        if (!(-1 <= E[i] && E[i] <= N))
            quit("Invalid argument");

    std::vector<int> S(N);
    for (int i = 0; i < N; i++)
        S[i] = (E[i] == -1 ? C[i] : E[i]);

    return count_components(S);
}
#endif

int CNT = 0;

int perform_experiment1(std::vector<int> E) {
    CNT++;
    if(CNT > 2750){
        while(true){

        }
    }
    return perform_experiment(E);
}

vector<vector<int>> v;
vector<int> used;

void dfs(int u){
    used[u] = 1;
    for(auto i : v[u]){
        if(!used[i]){
            dfs(i);
        }
    }
}

int n;
vector<int> c;

int get(int u){
    int l = 0, r = n;
    while(l + 1 != r){
        int m = (l + r) / 2;
        vector<int> e(n, n);
        int now = l;
        for(int i = 0; now < m; i++){
            if(i == u){
                continue;
            }
            e[i] = now++;
        }
        e[u] = -1;
        int x = perform_experiment1(e);
        if(x == m - l + 1){
            r = m;
        }else{
            l = m;
        }
    }
    return l;
}


vector<int> find_colours(int N, vector<int> x, vector<int> y){
    n = N;
    v.resize(n);
    for(int i = 0; i < x.size(); i++){
        v[x[i]].push_back(y[i]);
        v[y[i]].push_back(x[i]);
    }
    c.resize(n);
    for(int i = 0; i < n; i++){
        c[i] = get(i);
    }
    return c;
}

#ifdef lisie_bimbi

int main() {
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(nullptr)->sync_with_stdio(false);           
#endif
    assert(2 == scanf("%d%d", &N, &M));
    C.resize(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &C[i]));
    X.resize(M), Y.resize(M);
    for (int j = 0; j < M; j++)
        assert(2 == scanf("%d%d", &X[j], &Y[j]));
    fclose(stdin);

    adj.assign(N, std::vector<int>());
    for (int j = 0; j < M; j++) {
        adj[X[j]].push_back(Y[j]);
        adj[Y[j]].push_back(X[j]);
    }

    calls_cnt = 0;
    std::vector<int> G = find_colours(N, X, Y);

    int L = G.size();
    printf("%d %d\n", L, calls_cnt);
    for (int i = 0; i < L; i++)
        printf("%s%d", (i == 0 ? "" : " "), G[i]);
    printf("\n");
    fclose(stdout);

    return 0;
}

#endif

/*
signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(nullptr)->sync_with_stdio(false);           
#endif
    

    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
  
}
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1.5
Acceptable Answer

Test #1:

score: 1.5
Acceptable Answer
time: 1ms
memory: 3728kb

input:

1978433568
2
1
0
1
1978433568
1
1978433568
1

output:

877694080
-1
0
877694080
0
-1
877694081
1
1

result:

points 0.50 points  0.5

Test #2:

score: 1.5
Acceptable Answer
time: 1ms
memory: 3776kb

input:

1978433568
2
1
0
1
1978433568
1
1978433568
2

output:

877694080
-1
0
877694080
0
-1
877694081
1
0

result:

points 0.50 points  0.5

Test #3:

score: 1.5
Acceptable Answer
time: 0ms
memory: 4060kb

input:

1978433568
2
1
0
1
1978433568
2
1978433568
1

output:

877694080
-1
0
877694080
0
-1
877694081
0
1

result:

points 0.50 points  0.5

Test #4:

score: 1.5
Acceptable Answer
time: 1ms
memory: 3776kb

input:

1978433568
2
1
0
1
1978433568
2
1978433568
2

output:

877694080
-1
0
877694080
0
-1
877694081
0
0

result:

points 0.50 points  0.5

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

50%
Acceptable Answer

Test #5:

score: 0
Wrong Answer
time: 3ms
memory: 3728kb

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:

877694080
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
877694080
-1
25
26
27
28
29
30
31
32
33
34
35
36
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50...

result:

wrong answer Vertices 23 and 24 do have the same color, but they do not in returned answer

Subtask #3:

score: 0
Wrong Answer

Test #34:

score: 0
Wrong Answer
time: 30ms
memory: 3824kb

input:

1978433568
250
249
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
49
50
...

output:

877694080
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

result:

wrong answer Vertices 7 and 8 do have the same color, but they do not in returned answer

Subtask #4:

score: 21
Accepted

Test #43:

score: 21
Accepted
time: 50ms
memory: 4548kb

input:

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

output:

877694080
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

result:

ok #experiments: 2000

Test #44:

score: 21
Accepted
time: 35ms
memory: 4624kb

input:

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

output:

877694080
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

result:

ok #experiments: 1967

Test #45:

score: 21
Accepted
time: 48ms
memory: 4572kb

input:

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

output:

877694080
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

result:

ok #experiments: 2000

Test #46:

score: 21
Accepted
time: 38ms
memory: 4544kb

input:

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

output:

877694080
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

result:

ok #experiments: 2000

Test #47:

score: 21
Accepted
time: 29ms
memory: 4564kb

input:

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

output:

877694080
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

result:

ok #experiments: 1987

Test #48:

score: 21
Accepted
time: 39ms
memory: 4796kb

input:

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

output:

877694080
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

result:

ok #experiments: 1990

Test #49:

score: 21
Accepted
time: 32ms
memory: 4832kb

input:

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

output:

877694080
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

result:

ok #experiments: 1992

Test #50:

score: 21
Accepted
time: 41ms
memory: 4540kb

input:

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

output:

877694080
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

result:

ok #experiments: 2000

Test #51:

score: 21
Accepted
time: 36ms
memory: 4560kb

input:

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

output:

877694080
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

result:

ok #experiments: 1994

Subtask #5:

score: 0
Skipped

Dependency #1:

50%
Acceptable Answer

Dependency #2:

0%