oj.uz

Submission #1041736

# Submission time Handle Problem Language Result Execution time Memory
1041736 2024-08-02T07:35:59 Z 김은성(#11000) Brought Down the Grading Server? (CEOI23_balance) C++17
35 / 100
 27 ms 20692 KB 
#include <bits/stdc++.h>
using namespace std;
int n, s, t, *a[100009];
vector<pair<int, int> > graph[100009];
int ans[100009];
int deg[100009];
int cur[100009];
bool ch[100009];
void findcycle(int v){
	for(int i = cur[v]; i<graph[v].size(); i++){
		if(i < cur[v])
			i = cur[v];
		if(i == graph[v].size())
			break;
		auto [idx, u] = graph[v][i];
		cur[v]++;
		if(ans[idx] != -1)
			continue;
		ans[idx] = v;
		findcycle(u);
	}
}
void findpath(int v){
	ch[v]= 1;
	for(int i = cur[v]; i<graph[v].size(); i++){
		if(i < cur[v])
			i = cur[v];
		if(i == graph[v].size())
			break;
		auto [idx, u] = graph[v][i];
		cur[v]++;
		if(ans[idx] != -1)
			continue;
		ans[idx] = v;
		deg[v]++;
		deg[u]--;
		if(ch[u] || graph[u].size()%2 == 0){
			findpath(u);
			break;
		}
		else{
			ch[u] = 1;
			break;
		}
	}
}
void solve(int l, int r){
	int mid = (l+r)/2, delta = mid+1-l, i, j;
	vector<int> ver;
	for(i=0; i<n; i++){
		for(j=l; j<=r; j++){
			ver.push_back(a[i][j]);
			graph[a[i][j]].clear();
		}
	}
	for(i=0; i<n; i++){
		for(j=l; j<=mid; j++){
			graph[a[i][j]].push_back(make_pair(i*s + j, a[i][j+delta]));
			graph[a[i][j+delta]].push_back(make_pair(i*s + j, a[i][j]));
			ans[i*s+j] = -1;
		}
	}
	for(int i: ver)
		ch[i] = cur[i] = 0;
	for(int i: ver){
		if(graph[i].size()%2 == 1 && !ch[i])
			findpath(i), ch[i]=1;
	}
	for(int i: ver)
		cur[i] = 0;
	for(int i: ver){
		findcycle(i);
	}
	for(i=0; i<n; i++){
		for(j=l; j<=mid; j++){
			if(ans[i*s+j] == a[i][j])
				continue;
			swap(a[i][j], a[i][j+delta]);
		}
	}
	if(r-l==1)
		return;
	solve(l,mid);
	solve(mid+1,r);
}
int main(){
	int i, j;
	scanf("%d %d %d", &n, &s, &t);
	memset(ans, -1, sizeof(ans));
	for(i=0; i<n; i++){
		a[i] = (int*)malloc(s * sizeof(int));
		for(j=0; j<s; j++){
			scanf("%d", &a[i][j]);
		}
	}
	solve(0, s-1);
	for(i=0; i<n; i++){
		for(j=0; j<s; j++){
			printf("%d ", a[i][j]);
		}
		printf("\n");
	}
	return 0;
}

Compilation message

balance.cpp: In function 'void findcycle(int)':
balance.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(int i = cur[v]; i<graph[v].size(); i++){
      |                      ~^~~~~~~~~~~~~~~~
balance.cpp:13:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   if(i == graph[v].size())
      |      ~~^~~~~~~~~~~~~~~~~~
balance.cpp: In function 'void findpath(int)':
balance.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = cur[v]; i<graph[v].size(); i++){
      |                      ~^~~~~~~~~~~~~~~~
balance.cpp:28:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   if(i == graph[v].size())
      |      ~~^~~~~~~~~~~~~~~~~~
balance.cpp: In function 'void solve(int, int)':
balance.cpp:64:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   64 |   ch[i] = cur[i] = 0;
      |           ~~~~~~~^~~
balance.cpp: In function 'int main()':
balance.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d %d %d", &n, &s, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
balance.cpp:93:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |    scanf("%d", &a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 0 ms 4444 KB Correct

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Correct
2 Correct 0 ms 4444 KB Correct
3 Correct 1 ms 4444 KB Correct
4 Correct 1 ms 4444 KB Correct
5 Correct 1 ms 4444 KB Correct
6 Correct 1 ms 4444 KB Correct
7 Correct 0 ms 4444 KB Correct

Subtask #2-1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 20692 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 20692 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Correct
2 Correct 0 ms 4444 KB Correct
3 Correct 1 ms 4444 KB Correct
4 Correct 1 ms 4444 KB Correct
5 Correct 1 ms 4444 KB Correct
6 Correct 1 ms 4444 KB Correct
7 Correct 0 ms 4444 KB Correct
8 Runtime error 27 ms 20692 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3-1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Correct
2 Correct 4 ms 5212 KB Correct
3 Correct 4 ms 5144 KB Correct
4 Correct 2 ms 5212 KB Correct
5 Correct 2 ms 5208 KB Correct
6 Correct 3 ms 5208 KB Correct
7 Correct 2 ms 5208 KB Correct
8 Correct 3 ms 5212 KB Correct
9 Correct 2 ms 4956 KB Correct
10 Correct 3 ms 5212 KB Correct
11 Correct 2 ms 4956 KB Correct
12 Correct 2 ms 5212 KB Correct
13 Correct 2 ms 5212 KB Correct
14 Correct 2 ms 5212 KB Correct

Subtask #3-2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Correct
2 Correct 4 ms 5212 KB Correct
3 Correct 4 ms 5144 KB Correct
4 Correct 2 ms 5212 KB Correct
5 Correct 2 ms 5208 KB Correct
6 Correct 3 ms 5208 KB Correct
7 Correct 2 ms 5208 KB Correct
8 Correct 3 ms 5212 KB Correct
9 Correct 2 ms 4956 KB Correct
10 Correct 3 ms 5212 KB Correct
11 Correct 2 ms 4956 KB Correct
12 Correct 2 ms 5212 KB Correct
13 Correct 2 ms 5212 KB Correct
14 Correct 2 ms 5212 KB Correct
15 Correct 1 ms 4444 KB Correct
16 Correct 3 ms 5176 KB Correct
17 Correct 5 ms 4956 KB Correct
18 Correct 3 ms 5212 KB Correct
19 Correct 2 ms 5212 KB Correct
20 Correct 2 ms 5212 KB Correct
21 Correct 3 ms 5212 KB Correct
22 Correct 3 ms 5212 KB Correct
23 Correct 3 ms 4956 KB Correct
24 Correct 3 ms 5208 KB Correct
25 Correct 2 ms 4952 KB Correct
26 Correct 3 ms 5208 KB Correct
27 Correct 2 ms 5212 KB Correct
28 Correct 2 ms 5212 KB Correct
29 Correct 4 ms 5212 KB Correct
30 Correct 3 ms 4700 KB Correct
31 Correct 3 ms 4952 KB Correct
32 Correct 3 ms 4952 KB Correct

Subtask #3-3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Correct
2 Correct 4 ms 5212 KB Correct
3 Correct 4 ms 5144 KB Correct
4 Correct 2 ms 5212 KB Correct
5 Correct 2 ms 5208 KB Correct
6 Correct 3 ms 5208 KB Correct
7 Correct 2 ms 5208 KB Correct
8 Correct 3 ms 5212 KB Correct
9 Correct 2 ms 4956 KB Correct
10 Correct 3 ms 5212 KB Correct
11 Correct 2 ms 4956 KB Correct
12 Correct 2 ms 5212 KB Correct
13 Correct 2 ms 5212 KB Correct
14 Correct 2 ms 5212 KB Correct
15 Correct 1 ms 4444 KB Correct
16 Correct 3 ms 5176 KB Correct
17 Correct 5 ms 4956 KB Correct
18 Correct 3 ms 5212 KB Correct
19 Correct 2 ms 5212 KB Correct
20 Correct 2 ms 5212 KB Correct
21 Correct 3 ms 5212 KB Correct
22 Correct 3 ms 5212 KB Correct
23 Correct 3 ms 4956 KB Correct
24 Correct 3 ms 5208 KB Correct
25 Correct 2 ms 4952 KB Correct
26 Correct 3 ms 5208 KB Correct
27 Correct 2 ms 5212 KB Correct
28 Correct 2 ms 5212 KB Correct
29 Correct 4 ms 5212 KB Correct
30 Correct 3 ms 4700 KB Correct
31 Correct 3 ms 4952 KB Correct
32 Correct 3 ms 4952 KB Correct
33 Correct 1 ms 4444 KB Correct
34 Correct 3 ms 5048 KB Correct
35 Correct 4 ms 4956 KB Correct
36 Correct 2 ms 5212 KB Correct
37 Correct 2 ms 5212 KB Correct
38 Correct 4 ms 5212 KB Correct
39 Correct 2 ms 5212 KB Correct
40 Correct 3 ms 5212 KB Correct
41 Correct 3 ms 4956 KB Correct
42 Correct 3 ms 5212 KB Correct
43 Correct 2 ms 4956 KB Correct
44 Correct 2 ms 5212 KB Correct
45 Correct 2 ms 5212 KB Correct
46 Correct 2 ms 5212 KB Correct
47 Correct 4 ms 5212 KB Correct
48 Correct 3 ms 4700 KB Correct
49 Correct 3 ms 4956 KB Correct
50 Correct 3 ms 4956 KB Correct
51 Correct 1 ms 4444 KB Correct
52 Correct 1 ms 4532 KB Correct
53 Correct 1 ms 4444 KB Correct
54 Correct 1 ms 4444 KB Correct
55 Correct 1 ms 4444 KB Correct
56 Correct 1 ms 4444 KB Correct
57 Correct 1 ms 4440 KB Correct
58 Correct 4 ms 5212 KB Correct
59 Correct 4 ms 4956 KB Correct
60 Correct 3 ms 4848 KB Correct
61 Correct 3 ms 5124 KB Correct

Subtask #4-1
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 20692 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4-2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 20692 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4-3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 0 ms 4444 KB Correct
3 Correct 1 ms 4440 KB Correct
4 Correct 0 ms 4444 KB Correct
5 Correct 1 ms 4444 KB Correct
6 Correct 1 ms 4444 KB Correct
7 Correct 1 ms 4444 KB Correct
8 Correct 1 ms 4444 KB Correct
9 Correct 0 ms 4444 KB Correct
10 Runtime error 27 ms 20692 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -