oj.uz

Submission #965653

# Submission time Handle Problem Language Result Execution time Memory
965653 2024-04-19T03:40:56 Z fzyzzz_z Saveit (IOI10_saveit) C++17
50 / 100
 2131 ms 23792 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]; 
	string ans = ""; 
 
	vector<int> ord(nh); 
	for (int i = 0; i < nh; ++i) ord[i] = i; 
 
	for (int t = 0; t < 10; ++t) {
		string res = ""; 
		random_shuffle(ord.begin(), ord.end()); 
		
		for (int i = 0; i < nh; ++i) {
			for (int j = 0; j < n; ++j) {
				d[i][j] = inf; 
			}
		}
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				g[i][j] &= 1; 
			}
		}
 
		for (int i: ord) {
			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] == 3) {
							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] = 3; 
							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] == 3; 
			}
			if (n < c * 11) {
				// encode_bit(0); 
				res += '0';
				for (int j = i + 1; j < n; ++j) {
					// encode_bit(g[i][j] == 3); 
					res += '0' + (g[i][j] == 3); 
				}
			} else {
				// encode_bit(1); 
				res += '1'; 
				int mx = 0; 
				for (int j = i + 1; j < n; ++j) if (g[i][j] == 3) mx = j; 
				for (int j = i + 1; j < n; ++j) {
					if (g[i][j] != 3) continue; 
					// encode_bit(1); 
					res += '1';
					for (int b = 0; b < 10; ++b) {
						// encode_bit(((1 << b) & j) >> b); 
						res += '0'+ (((1 << b) & j) >> b); 
					}
				}
				// encode_bit(0); 
				res += '0';
			}
		}
		if (res.size() < ans.size() || ans.size() == 0) ans = res; 
	}
	

	for (auto x: ans) encode_bit(x != '0' ? 1 : 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; 
// }

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:85:9: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
   85 |     int mx = 0;
      |         ^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2044 ms 17392 KB Output is correct - 37540 call(s) of encode_bit()
2 Correct 3 ms 8712 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 1666 ms 11676 KB Output is correct - 39816 call(s) of encode_bit()
4 Correct 2 ms 4620 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 1653 ms 14056 KB Output is partially correct - 85466 call(s) of encode_bit()
6 Correct 2025 ms 15568 KB Output is partially correct - 87162 call(s) of encode_bit()
7 Correct 2011 ms 16368 KB Output is partially correct - 164470 call(s) of encode_bit()
8 Correct 1941 ms 14808 KB Output is correct - 19313 call(s) of encode_bit()
9 Correct 2101 ms 19556 KB Output is correct - 19226 call(s) of encode_bit()
10 Correct 2107 ms 19328 KB Output is correct - 18885 call(s) of encode_bit()
11 Correct 2089 ms 19380 KB Output is correct - 34719 call(s) of encode_bit()
12 Correct 2131 ms 19516 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 1994 ms 19736 KB Output is partially correct - 92287 call(s) of encode_bit()
14 Correct 2092 ms 19488 KB Output is correct - 22779 call(s) of encode_bit()
15 Correct 2100 ms 19272 KB Output is correct - 25302 call(s) of encode_bit()
16 Correct 2072 ms 19512 KB Output is correct - 42340 call(s) of encode_bit()
17 Correct 2075 ms 19588 KB Output is correct - 30901 call(s) of encode_bit()
18 Correct 2044 ms 19568 KB Output is correct - 52291 call(s) of encode_bit()
19 Correct 2046 ms 19804 KB Output is correct - 67002 call(s) of encode_bit()
20 Correct 2025 ms 21688 KB Output is correct - 63631 call(s) of encode_bit()
21 Correct 2027 ms 21720 KB Output is correct - 60858 call(s) of encode_bit()
22 Correct 1996 ms 21776 KB Output is partially correct - 133999 call(s) of encode_bit()
23 Correct 2012 ms 23792 KB Output is partially correct - 94898 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2044 ms 17392 KB Output is correct - 37540 call(s) of encode_bit()
2 Correct 3 ms 8712 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 1666 ms 11676 KB Output is correct - 39816 call(s) of encode_bit()
4 Correct 2 ms 4620 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 1653 ms 14056 KB Output is partially correct - 85466 call(s) of encode_bit()
6 Correct 2025 ms 15568 KB Output is partially correct - 87162 call(s) of encode_bit()
7 Correct 2011 ms 16368 KB Output is partially correct - 164470 call(s) of encode_bit()
8 Correct 1941 ms 14808 KB Output is correct - 19313 call(s) of encode_bit()
9 Correct 2101 ms 19556 KB Output is correct - 19226 call(s) of encode_bit()
10 Correct 2107 ms 19328 KB Output is correct - 18885 call(s) of encode_bit()
11 Correct 2089 ms 19380 KB Output is correct - 34719 call(s) of encode_bit()
12 Correct 2131 ms 19516 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 1994 ms 19736 KB Output is partially correct - 92287 call(s) of encode_bit()
14 Correct 2092 ms 19488 KB Output is correct - 22779 call(s) of encode_bit()
15 Correct 2100 ms 19272 KB Output is correct - 25302 call(s) of encode_bit()
16 Correct 2072 ms 19512 KB Output is correct - 42340 call(s) of encode_bit()
17 Correct 2075 ms 19588 KB Output is correct - 30901 call(s) of encode_bit()
18 Correct 2044 ms 19568 KB Output is correct - 52291 call(s) of encode_bit()
19 Correct 2046 ms 19804 KB Output is correct - 67002 call(s) of encode_bit()
20 Correct 2025 ms 21688 KB Output is correct - 63631 call(s) of encode_bit()
21 Correct 2027 ms 21720 KB Output is correct - 60858 call(s) of encode_bit()
22 Correct 1996 ms 21776 KB Output is partially correct - 133999 call(s) of encode_bit()
23 Correct 2012 ms 23792 KB Output is partially correct - 94898 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2044 ms 17392 KB Output is correct - 37540 call(s) of encode_bit()
2 Correct 3 ms 8712 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 1666 ms 11676 KB Output is correct - 39816 call(s) of encode_bit()
4 Correct 2 ms 4620 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 1653 ms 14056 KB Output is partially correct - 85466 call(s) of encode_bit()
6 Correct 2025 ms 15568 KB Output is partially correct - 87162 call(s) of encode_bit()
7 Correct 2011 ms 16368 KB Output is partially correct - 164470 call(s) of encode_bit()
8 Correct 1941 ms 14808 KB Output is correct - 19313 call(s) of encode_bit()
9 Correct 2101 ms 19556 KB Output is correct - 19226 call(s) of encode_bit()
10 Correct 2107 ms 19328 KB Output is correct - 18885 call(s) of encode_bit()
11 Correct 2089 ms 19380 KB Output is correct - 34719 call(s) of encode_bit()
12 Correct 2131 ms 19516 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 1994 ms 19736 KB Output is partially correct - 92287 call(s) of encode_bit()
14 Correct 2092 ms 19488 KB Output is correct - 22779 call(s) of encode_bit()
15 Correct 2100 ms 19272 KB Output is correct - 25302 call(s) of encode_bit()
16 Correct 2072 ms 19512 KB Output is correct - 42340 call(s) of encode_bit()
17 Correct 2075 ms 19588 KB Output is correct - 30901 call(s) of encode_bit()
18 Correct 2044 ms 19568 KB Output is correct - 52291 call(s) of encode_bit()
19 Correct 2046 ms 19804 KB Output is correct - 67002 call(s) of encode_bit()
20 Correct 2025 ms 21688 KB Output is correct - 63631 call(s) of encode_bit()
21 Correct 2027 ms 21720 KB Output is correct - 60858 call(s) of encode_bit()
22 Correct 1996 ms 21776 KB Output is partially correct - 133999 call(s) of encode_bit()
23 Correct 2012 ms 23792 KB Output is partially correct - 94898 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2044 ms 17392 KB Output is correct - 37540 call(s) of encode_bit()
2 Correct 3 ms 8712 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 1666 ms 11676 KB Output is correct - 39816 call(s) of encode_bit()
4 Correct 2 ms 4620 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 1653 ms 14056 KB Output is partially correct - 85466 call(s) of encode_bit()
6 Correct 2025 ms 15568 KB Output is partially correct - 87162 call(s) of encode_bit()
7 Correct 2011 ms 16368 KB Output is partially correct - 164470 call(s) of encode_bit()
8 Correct 1941 ms 14808 KB Output is correct - 19313 call(s) of encode_bit()
9 Correct 2101 ms 19556 KB Output is correct - 19226 call(s) of encode_bit()
10 Correct 2107 ms 19328 KB Output is correct - 18885 call(s) of encode_bit()
11 Correct 2089 ms 19380 KB Output is correct - 34719 call(s) of encode_bit()
12 Correct 2131 ms 19516 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 1994 ms 19736 KB Output is partially correct - 92287 call(s) of encode_bit()
14 Correct 2092 ms 19488 KB Output is correct - 22779 call(s) of encode_bit()
15 Correct 2100 ms 19272 KB Output is correct - 25302 call(s) of encode_bit()
16 Correct 2072 ms 19512 KB Output is correct - 42340 call(s) of encode_bit()
17 Correct 2075 ms 19588 KB Output is correct - 30901 call(s) of encode_bit()
18 Correct 2044 ms 19568 KB Output is correct - 52291 call(s) of encode_bit()
19 Correct 2046 ms 19804 KB Output is correct - 67002 call(s) of encode_bit()
20 Correct 2025 ms 21688 KB Output is correct - 63631 call(s) of encode_bit()
21 Correct 2027 ms 21720 KB Output is correct - 60858 call(s) of encode_bit()
22 Correct 1996 ms 21776 KB Output is partially correct - 133999 call(s) of encode_bit()
23 Correct 2012 ms 23792 KB Output is partially correct - 94898 call(s) of encode_bit()