QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#553356	#9241. Sphinx	thomaswmy^#	36	125ms	4608kb	C++17	2.8kb	2024-09-08 12:12:30	2024-09-08 12:12:31

Judging History

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

[2024-09-08 12:12:31]
评测

测评结果：36
用时：125ms
内存：4608kb

查看

[2024-09-08 12:12:30]
提交

answer

#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
const int NN=260;

int n;
vector<int> g[NN],gc[NN];
int tot;
bool vis[NN];
int cc[NN],ctot,rc[NN];
vector<int> c[NN];

void dfs(int u,vector<int> &col) {
  vis[u]=1;
  for(int v:g[u]) {
    if(vis[v]) continue;
    if(col[u]!=col[v]) continue;
    dfs(v,col);
  }
}

int calc(vector<int> &col) {
  for(int i=0;i<n;i++) vis[i]=0;
  int res=0;
  for(int i=0;i<n;i++) {
    if(vis[i]) continue;
    dfs(i,col);
    res++;
  }
  return res;
}

int solve(vector<int> &arr,int col,int L,int R) {
  if(L==R) return L;
  vector<int> a,b;
  a.resize(n,col);
  b.resize(n,col);
  int mid=L+R>>1;
  for(int i=L;i<=mid;i++) a[arr[i]]=n,b[arr[i]]=-1;
  int val1=calc(a),val2=perform_experiment(b);
  if(val1!=val2) return solve(arr,col,L,mid);
  else return solve(arr,col,mid+1,R);
}

vector<int> find_colours(int N,vector<int> X,vector<int> Y) {
    n=N;
    vector<int> col;
    col.resize(n);
    int m=X.size();
    for(int i=0;i<m;i++) {
      if(X[i]>Y[i]) swap(X[i],Y[i]);
      g[X[i]].push_back(Y[i]),g[Y[i]].push_back(X[i]);
    }
    for(int i=0;i<2;i++) {
      vector<int> arr;
      for(int j=i;j<n;j+=2) arr.push_back(j);
      for(int j=0;j<n;j++) {
        while(arr.size()) {
          vector<int> a,b;
          a.resize(n,j),b.resize(n,j);
          for(int k:arr) a[k]=n,b[k]=-1;
          if(calc(a)==perform_experiment(b)) break;
          int ps=solve(arr,j,0,arr.size());
          col[arr[ps]]=j;
          vector<int> arrr;
          for(int k:arr) if(k!=arr[ps]) arrr.push_back(k);
          swap(arr,arrr);
        }
      }
    }
    return col;
    // tot=0;
    // for(int i=1;i<n;i++) {
    //   col[i]=++tot;
    //   sort(g[i].begin(),g[i].end());
    //   do{
    //     vector<int> arr;
    //     for(int j:g[i]) {
    //       if(j<i && col[j]!=col[i]) arr.push_back(j);
    //     }
    //     vector<int> a,b;
    //     a.resize(n,n),b.resize(n,n);
    //     for(int j:arr) a[j]=col[j],b[j]=-1;
    //     a[i]=col[i],b[i]=-1;
    //     if(calc(a)==perform_experiment(b)) break;
    //     int val=solve(i,arr,col,0,arr.size()-1);
    //     if(val==-1) break;
    //     for(int j=0;j<n;j++) if(col[j]==val) col[j]=col[i]; 
    //   }while(1);
    // }
    // for(int i=0;i<n;i++) vis[i]=0;
    // ctot=0;
    // for(int i=0;i<n;i++) {
    //   if(vis[i]) continue;
    //   ctot++;
    //   dfss(i,col,ctot);
    // }
    // if(ctot==1) {
    //   for(int i=0;i<n;i++) {
    //     vector<int> b;
    //     b.resize(n,-1);
    //     b[0]=i;
    //     if(perform_experiment(b)==1) {
    //       vector<int> res;
    //       res.resize(n,i);
    //       return res;
    //     }
    //   }
    // }
    // for(int i=0;i<n;i++) col[i]=rc[cc[i]];
    // return col;
}

源文件, 语言: C++17

詳細信息

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 1ms

memory: 3792kb

input:

output:

result:

ok #experiments: 4

Test #2:

score: 3

Accepted

time: 1ms

memory: 4084kb

input:

output:

result:

ok #experiments: 5

Test #3:

score: 3

Accepted

time: 1ms

memory: 4036kb

input:

output:

result:

ok #experiments: 5

Test #4:

score: 3

Accepted

time: 0ms

memory: 3796kb

input:

output:

result:

ok #experiments: 6

Subtask #2:

score: 0

Runtime Error

Dependency #1:

100%

Accepted

Test #5:

score: 7

Accepted

time: 2ms

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

Test #6:

score: 7

Accepted

time: 3ms

memory: 3824kb

input:

output:

result:

ok #experiments: 323

Test #7:

score: 7

Accepted

time: 3ms

memory: 3696kb

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

Test #8:

score: 7

Accepted

time: 3ms

memory: 4060kb

input:

output:

result:

ok #experiments: 311

Test #9:

score: 7

Accepted

time: 0ms

memory: 4052kb

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

Test #10:

score: 7

Accepted

time: 1ms

memory: 3828kb

input:

output:

result:

ok #experiments: 325

Test #11:

score: 7

Accepted

time: 0ms

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

Test #12:

score: 7

Accepted

time: 3ms

memory: 3756kb

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

Test #13:

score: 0

Runtime Error

input:

output:

result:

Subtask #3:

score: 33

Accepted

Test #34:

score: 33

Accepted

time: 37ms

memory: 3792kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 1978

Test #35:

score: 33

Accepted

time: 45ms

memory: 4132kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 2200

Test #36:

score: 33

Accepted

time: 33ms

memory: 3796kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 2149

Test #37:

score: 33

Accepted

time: 22ms

memory: 3840kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 2161

Test #38:

score: 33

Accepted

time: 43ms

memory: 3840kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 2135

Test #39:

score: 33

Accepted

time: 35ms

memory: 4124kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 2171

Test #40:

score: 33

Accepted

time: 46ms

memory: 4128kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 2175

Test #41:

score: 33

Accepted

time: 34ms

memory: 3864kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 2026

Test #42:

score: 33

Accepted

time: 39ms

memory: 4092kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 2154

Subtask #4:

score: 0

Wrong Answer

Test #43:

score: 0

Wrong Answer

time: 125ms

memory: 4608kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

wrong answer Vertices 0 and 3 do have the same color, but they do not in returned answer

Subtask #5:

score: 0

Skipped

Dependency #1:

100%

Accepted