oj.uz

Submission #965647

# Submission time Handle Problem Language Result Execution time Memory
965647 2024-04-19T03:33:27 Z fzyzzz_z Saveit (IOI10_saveit) C++17
0 / 100
 10000 ms 12996 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 < 2; ++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] == 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 * 11) {
				// encode_bit(0); 
				res += '0';
				for (int j = i + 1; j < n; ++j) {
					// encode_bit(g[i][j] == 2); 
					res += '0' + (g[i][j] == 2); 
				}
			} else {
				// encode_bit(1); 
				res += '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; 
					// 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'); 


	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:26:26: warning: for increment expression has no effect [-Wunused-value]
   26 |  for (int i = 0; i < nh; +i) ord[i] = i;
      |                          ^~
encoder.cpp:85:9: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
   85 |     int mx = 0;
      |         ^~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10079 ms 12624 KB Time limit exceeded
2 Execution timed out 10095 ms 6488 KB Time limit exceeded
3 Execution timed out 10033 ms 9816 KB Time limit exceeded
4 Execution timed out 10046 ms 6488 KB Time limit exceeded
5 Execution timed out 10027 ms 9952 KB Time limit exceeded
6 Execution timed out 10025 ms 10720 KB Time limit exceeded
7 Execution timed out 10023 ms 10976 KB Time limit exceeded
8 Execution timed out 10028 ms 10324 KB Time limit exceeded
9 Execution timed out 10023 ms 10584 KB Time limit exceeded
10 Execution timed out 10084 ms 10440 KB Time limit exceeded
11 Execution timed out 10010 ms 10464 KB Time limit exceeded
12 Execution timed out 10033 ms 10584 KB Time limit exceeded
13 Execution timed out 10006 ms 10548 KB Time limit exceeded
14 Execution timed out 10085 ms 10444 KB Time limit exceeded
15 Execution timed out 10041 ms 10460 KB Time limit exceeded
16 Execution timed out 10087 ms 8728 KB Time limit exceeded
17 Execution timed out 10053 ms 9212 KB Time limit exceeded
18 Execution timed out 10039 ms 8776 KB Time limit exceeded
19 Execution timed out 10018 ms 9036 KB Time limit exceeded
20 Execution timed out 10074 ms 7312 KB Time limit exceeded
21 Execution timed out 10020 ms 12996 KB Time limit exceeded
22 Execution timed out 10031 ms 10548 KB Time limit exceeded
23 Execution timed out 10036 ms 12828 KB Time limit exceeded

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10079 ms 12624 KB Time limit exceeded
2 Execution timed out 10095 ms 6488 KB Time limit exceeded
3 Execution timed out 10033 ms 9816 KB Time limit exceeded
4 Execution timed out 10046 ms 6488 KB Time limit exceeded
5 Execution timed out 10027 ms 9952 KB Time limit exceeded
6 Execution timed out 10025 ms 10720 KB Time limit exceeded
7 Execution timed out 10023 ms 10976 KB Time limit exceeded
8 Execution timed out 10028 ms 10324 KB Time limit exceeded
9 Execution timed out 10023 ms 10584 KB Time limit exceeded
10 Execution timed out 10084 ms 10440 KB Time limit exceeded
11 Execution timed out 10010 ms 10464 KB Time limit exceeded
12 Execution timed out 10033 ms 10584 KB Time limit exceeded
13 Execution timed out 10006 ms 10548 KB Time limit exceeded
14 Execution timed out 10085 ms 10444 KB Time limit exceeded
15 Execution timed out 10041 ms 10460 KB Time limit exceeded
16 Execution timed out 10087 ms 8728 KB Time limit exceeded
17 Execution timed out 10053 ms 9212 KB Time limit exceeded
18 Execution timed out 10039 ms 8776 KB Time limit exceeded
19 Execution timed out 10018 ms 9036 KB Time limit exceeded
20 Execution timed out 10074 ms 7312 KB Time limit exceeded
21 Execution timed out 10020 ms 12996 KB Time limit exceeded
22 Execution timed out 10031 ms 10548 KB Time limit exceeded
23 Execution timed out 10036 ms 12828 KB Time limit exceeded

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10079 ms 12624 KB Time limit exceeded
2 Execution timed out 10095 ms 6488 KB Time limit exceeded
3 Execution timed out 10033 ms 9816 KB Time limit exceeded
4 Execution timed out 10046 ms 6488 KB Time limit exceeded
5 Execution timed out 10027 ms 9952 KB Time limit exceeded
6 Execution timed out 10025 ms 10720 KB Time limit exceeded
7 Execution timed out 10023 ms 10976 KB Time limit exceeded
8 Execution timed out 10028 ms 10324 KB Time limit exceeded
9 Execution timed out 10023 ms 10584 KB Time limit exceeded
10 Execution timed out 10084 ms 10440 KB Time limit exceeded
11 Execution timed out 10010 ms 10464 KB Time limit exceeded
12 Execution timed out 10033 ms 10584 KB Time limit exceeded
13 Execution timed out 10006 ms 10548 KB Time limit exceeded
14 Execution timed out 10085 ms 10444 KB Time limit exceeded
15 Execution timed out 10041 ms 10460 KB Time limit exceeded
16 Execution timed out 10087 ms 8728 KB Time limit exceeded
17 Execution timed out 10053 ms 9212 KB Time limit exceeded
18 Execution timed out 10039 ms 8776 KB Time limit exceeded
19 Execution timed out 10018 ms 9036 KB Time limit exceeded
20 Execution timed out 10074 ms 7312 KB Time limit exceeded
21 Execution timed out 10020 ms 12996 KB Time limit exceeded
22 Execution timed out 10031 ms 10548 KB Time limit exceeded
23 Execution timed out 10036 ms 12828 KB Time limit exceeded

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10079 ms 12624 KB Time limit exceeded
2 Execution timed out 10095 ms 6488 KB Time limit exceeded
3 Execution timed out 10033 ms 9816 KB Time limit exceeded
4 Execution timed out 10046 ms 6488 KB Time limit exceeded
5 Execution timed out 10027 ms 9952 KB Time limit exceeded
6 Execution timed out 10025 ms 10720 KB Time limit exceeded
7 Execution timed out 10023 ms 10976 KB Time limit exceeded
8 Execution timed out 10028 ms 10324 KB Time limit exceeded
9 Execution timed out 10023 ms 10584 KB Time limit exceeded
10 Execution timed out 10084 ms 10440 KB Time limit exceeded
11 Execution timed out 10010 ms 10464 KB Time limit exceeded
12 Execution timed out 10033 ms 10584 KB Time limit exceeded
13 Execution timed out 10006 ms 10548 KB Time limit exceeded
14 Execution timed out 10085 ms 10444 KB Time limit exceeded
15 Execution timed out 10041 ms 10460 KB Time limit exceeded
16 Execution timed out 10087 ms 8728 KB Time limit exceeded
17 Execution timed out 10053 ms 9212 KB Time limit exceeded
18 Execution timed out 10039 ms 8776 KB Time limit exceeded
19 Execution timed out 10018 ms 9036 KB Time limit exceeded
20 Execution timed out 10074 ms 7312 KB Time limit exceeded
21 Execution timed out 10020 ms 12996 KB Time limit exceeded
22 Execution timed out 10031 ms 10548 KB Time limit exceeded
23 Execution timed out 10036 ms 12828 KB Time limit exceeded