oj.uz

Submission #965634

# Submission time Handle Problem Language Result Execution time Memory
965634 2024-04-19T03:22:23 Z fzyzzz_z Saveit (IOI10_saveit) C++17
0 / 100
 333 ms 34044 KB 
#include <bits/stdc++.h>
using namespace std; 

#include "grader.h"
#include "encoder.h"

// vector<int> bits; 
// void encode_bit(int x) { bits.push_back(x); }

void encode(int n, int nh, int ne, int *v1, int *v2){
	int g[n][n]; 
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			g[i][j] = 0; 
		}
	}
	for (int i = 0; i < ne; ++i) {
		g[v1[i]][v2[i]] = g[v2[i]][v1[i]] = 1; 
	}

	int inf = 1e9; 
	int d[nh][n]; 
	for (int i = 0; i < nh; ++i) {
		for (int j = 0; j < n; ++j) {
			d[i][j] = inf; 
		}
	}

	for (int i = 0; i < nh; ++i) {
		vector<int> c(1, i); 
		d[i][i] = 0; 

		for (int cd = 0; cd < n; ++cd) {
			vector<int> nc; 
			for (auto x: c) {
				for (int y = 0; y < n; ++y) {
					if (d[i][y] == inf && g[x][y] == 2) {
						d[i][y] = cd + 1; 
						nc.push_back(y); 
					}	
				}
			}
			for (auto x: c) {
				for (int y = 0; y < n; ++y) {
					if (d[i][y] == inf && g[x][y] == 1) {
						d[i][y] = cd + 1; 
						g[x][y] = g[y][x] = 2; 
						nc.push_back(y); 
					}	
				}
			}
			c = nc; 
		}
	}

	for (int i = 0; i < n; ++i) {
		int c = 0; 
		for (int j = i + 1; j < n; ++j) {
			c += g[i][j] == 2; 
		}
		if (n < c * 10) {
			encode_bit(0); 
			for (int j = i + 1; j < n; ++j) {
				encode_bit(g[i][j] == 2); 
			}
		} else {
			encode_bit(1); 
			int mx = 0; 
			for (int j = i + 1; j < n; ++j) if (g[i][j] == 2) mx = j; 
			for (int j = i + 1; j < n; ++j) {
				if (g[i][j] != 2) continue; 
				if (j < mx) encode_bit(1); 
				for (int b = 0; b < 10; ++b) {
					encode_bit(((1 << b) & j) >> b); 
				}
			}
			encode_bit(0); 
		}
	}



	return;
}

// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	int n, k, p; 
// 	cin >> n >> k >> p; 
// 	int a[p], b[p]; 
// 	for (int i = 0; i < p; ++i) cin >> a[i] >> b[i]; 

// 	encode(n, k, p, a, b); 
// 	for (int i = 0; i < bits.size(); ++i) cout << bits[i]; 
// 	cout << '\n';

// 	return 0; 
// }



#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;

// string ss; 
// int decode_bit() { char c = ss.back(); ss.pop_back(); return c != '0'; } 
// void hops(int k, int i, int d) {
// 	cout << k << ' ' << i << ' ' << d << '\n';
// }

void decode(int n, int nh) {
	int g[n][n]; 
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			g[i][j] = 0; 
		}
	}
	for (int i = 0; i < n; ++i) {
		int t = decode_bit(); 
		if (t == 0) {
			for (int j = i + 1; j < n; ++j) {
				if (decode_bit()) {
					g[i][j] = g[j][i] = 1; 
					// cout << "! " << i << ' ' << j << '\n';
				}
			}
		} else {
			while (decode_bit()) {
				int x = 0; 
				for (int b = 0; b < 10; ++b) {
					x += (decode_bit() << b); 
				}
				g[i][x] = g[x][i] = 1; 
				// cout << "! " << i << ' ' << x << '\n';
			}
		}
	}

	for (int k = 0; k < nh; ++k) {
		vector<int> d(n, 1e9); 
		d[k] = 0; 
		queue<int> q; 
		q.push(k); 
		while (!q.empty()) {
			auto x = q.front(); 
			q.pop(); 
			for (int y = 0; y < n; ++y) {
				if (y != x && d[y] > n && g[x][y]) {
					d[y] = d[x] + 1; 
					q.push(y); 
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			hops(k, i, d[i]); 
		}
	}
}

// int main() {
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(0); 

// 	int n, k; 
// 	cin >> n >> k; 
// 	cin >> ss; 
// 	reverse(ss.begin(), ss.end()); 
	
// 	decode(n, k); 

// 	return 0; 
// }

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 333 ms 29944 KB Execution killed with signal 11
2 Correct 2 ms 11268 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 179 ms 25328 KB Execution killed with signal 11
4 Correct 2 ms 11272 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 179 ms 25464 KB Execution killed with signal 11
6 Runtime error 219 ms 27664 KB Execution killed with signal 11
7 Runtime error 244 ms 31924 KB Execution killed with signal 11
8 Runtime error 213 ms 26808 KB Execution killed with signal 11
9 Runtime error 234 ms 27616 KB Execution killed with signal 11
10 Incorrect 221 ms 19232 KB too many decode_bit() calls
11 Runtime error 228 ms 27620 KB Execution killed with signal 11
12 Incorrect 221 ms 19156 KB too many decode_bit() calls
13 Runtime error 238 ms 28288 KB Execution killed with signal 11
14 Incorrect 222 ms 19192 KB too many decode_bit() calls
15 Incorrect 220 ms 19228 KB too many decode_bit() calls
16 Runtime error 242 ms 27792 KB Execution killed with signal 11
17 Incorrect 231 ms 19276 KB too many decode_bit() calls
18 Incorrect 225 ms 19432 KB too many decode_bit() calls
19 Runtime error 236 ms 28056 KB Execution killed with signal 11
20 Runtime error 240 ms 30184 KB Execution killed with signal 11
21 Runtime error 250 ms 30044 KB Execution killed with signal 11
22 Runtime error 237 ms 32180 KB Execution killed with signal 11
23 Runtime error 248 ms 34044 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 333 ms 29944 KB Execution killed with signal 11
2 Correct 2 ms 11268 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 179 ms 25328 KB Execution killed with signal 11
4 Correct 2 ms 11272 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 179 ms 25464 KB Execution killed with signal 11
6 Runtime error 219 ms 27664 KB Execution killed with signal 11
7 Runtime error 244 ms 31924 KB Execution killed with signal 11
8 Runtime error 213 ms 26808 KB Execution killed with signal 11
9 Runtime error 234 ms 27616 KB Execution killed with signal 11
10 Incorrect 221 ms 19232 KB too many decode_bit() calls
11 Runtime error 228 ms 27620 KB Execution killed with signal 11
12 Incorrect 221 ms 19156 KB too many decode_bit() calls
13 Runtime error 238 ms 28288 KB Execution killed with signal 11
14 Incorrect 222 ms 19192 KB too many decode_bit() calls
15 Incorrect 220 ms 19228 KB too many decode_bit() calls
16 Runtime error 242 ms 27792 KB Execution killed with signal 11
17 Incorrect 231 ms 19276 KB too many decode_bit() calls
18 Incorrect 225 ms 19432 KB too many decode_bit() calls
19 Runtime error 236 ms 28056 KB Execution killed with signal 11
20 Runtime error 240 ms 30184 KB Execution killed with signal 11
21 Runtime error 250 ms 30044 KB Execution killed with signal 11
22 Runtime error 237 ms 32180 KB Execution killed with signal 11
23 Runtime error 248 ms 34044 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 333 ms 29944 KB Execution killed with signal 11
2 Correct 2 ms 11268 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 179 ms 25328 KB Execution killed with signal 11
4 Correct 2 ms 11272 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 179 ms 25464 KB Execution killed with signal 11
6 Runtime error 219 ms 27664 KB Execution killed with signal 11
7 Runtime error 244 ms 31924 KB Execution killed with signal 11
8 Runtime error 213 ms 26808 KB Execution killed with signal 11
9 Runtime error 234 ms 27616 KB Execution killed with signal 11
10 Incorrect 221 ms 19232 KB too many decode_bit() calls
11 Runtime error 228 ms 27620 KB Execution killed with signal 11
12 Incorrect 221 ms 19156 KB too many decode_bit() calls
13 Runtime error 238 ms 28288 KB Execution killed with signal 11
14 Incorrect 222 ms 19192 KB too many decode_bit() calls
15 Incorrect 220 ms 19228 KB too many decode_bit() calls
16 Runtime error 242 ms 27792 KB Execution killed with signal 11
17 Incorrect 231 ms 19276 KB too many decode_bit() calls
18 Incorrect 225 ms 19432 KB too many decode_bit() calls
19 Runtime error 236 ms 28056 KB Execution killed with signal 11
20 Runtime error 240 ms 30184 KB Execution killed with signal 11
21 Runtime error 250 ms 30044 KB Execution killed with signal 11
22 Runtime error 237 ms 32180 KB Execution killed with signal 11
23 Runtime error 248 ms 34044 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 333 ms 29944 KB Execution killed with signal 11
2 Correct 2 ms 11268 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 179 ms 25328 KB Execution killed with signal 11
4 Correct 2 ms 11272 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 179 ms 25464 KB Execution killed with signal 11
6 Runtime error 219 ms 27664 KB Execution killed with signal 11
7 Runtime error 244 ms 31924 KB Execution killed with signal 11
8 Runtime error 213 ms 26808 KB Execution killed with signal 11
9 Runtime error 234 ms 27616 KB Execution killed with signal 11
10 Incorrect 221 ms 19232 KB too many decode_bit() calls
11 Runtime error 228 ms 27620 KB Execution killed with signal 11
12 Incorrect 221 ms 19156 KB too many decode_bit() calls
13 Runtime error 238 ms 28288 KB Execution killed with signal 11
14 Incorrect 222 ms 19192 KB too many decode_bit() calls
15 Incorrect 220 ms 19228 KB too many decode_bit() calls
16 Runtime error 242 ms 27792 KB Execution killed with signal 11
17 Incorrect 231 ms 19276 KB too many decode_bit() calls
18 Incorrect 225 ms 19432 KB too many decode_bit() calls
19 Runtime error 236 ms 28056 KB Execution killed with signal 11
20 Runtime error 240 ms 30184 KB Execution killed with signal 11
21 Runtime error 250 ms 30044 KB Execution killed with signal 11
22 Runtime error 237 ms 32180 KB Execution killed with signal 11
23 Runtime error 248 ms 34044 KB Execution killed with signal 11