oj.uz

Submission #965645

# Submission time Handle Problem Language Result Execution time Memory
965645 2024-04-19T03:31:52 Z fzyzzz_z Saveit (IOI10_saveit) C++17
0 / 100
 10000 ms 12832 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 < 5; ++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:84:9: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
   84 |     int mx = 0;
      |         ^~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10089 ms 12628 KB Time limit exceeded
2 Execution timed out 10047 ms 6488 KB Time limit exceeded
3 Execution timed out 10036 ms 9676 KB Time limit exceeded
4 Execution timed out 10029 ms 6488 KB Time limit exceeded
5 Execution timed out 10098 ms 9948 KB Time limit exceeded
6 Execution timed out 10095 ms 10464 KB Time limit exceeded
7 Execution timed out 10039 ms 10492 KB Time limit exceeded
8 Execution timed out 10019 ms 10328 KB Time limit exceeded
9 Execution timed out 10021 ms 10584 KB Time limit exceeded
10 Execution timed out 10005 ms 10444 KB Time limit exceeded
11 Execution timed out 10041 ms 10460 KB Time limit exceeded
12 Execution timed out 10070 ms 10584 KB Time limit exceeded
13 Execution timed out 10013 ms 10996 KB Time limit exceeded
14 Execution timed out 10031 ms 10444 KB Time limit exceeded
15 Execution timed out 10029 ms 10452 KB Time limit exceeded
16 Execution timed out 10080 ms 10560 KB Time limit exceeded
17 Execution timed out 10038 ms 10720 KB Time limit exceeded
18 Execution timed out 10042 ms 10692 KB Time limit exceeded
19 Execution timed out 10020 ms 10500 KB Time limit exceeded
20 Execution timed out 10035 ms 12832 KB Time limit exceeded
21 Execution timed out 10038 ms 12660 KB Time limit exceeded
22 Execution timed out 10101 ms 10732 KB Time limit exceeded
23 Execution timed out 10044 ms 11468 KB Time limit exceeded

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10089 ms 12628 KB Time limit exceeded
2 Execution timed out 10047 ms 6488 KB Time limit exceeded
3 Execution timed out 10036 ms 9676 KB Time limit exceeded
4 Execution timed out 10029 ms 6488 KB Time limit exceeded
5 Execution timed out 10098 ms 9948 KB Time limit exceeded
6 Execution timed out 10095 ms 10464 KB Time limit exceeded
7 Execution timed out 10039 ms 10492 KB Time limit exceeded
8 Execution timed out 10019 ms 10328 KB Time limit exceeded
9 Execution timed out 10021 ms 10584 KB Time limit exceeded
10 Execution timed out 10005 ms 10444 KB Time limit exceeded
11 Execution timed out 10041 ms 10460 KB Time limit exceeded
12 Execution timed out 10070 ms 10584 KB Time limit exceeded
13 Execution timed out 10013 ms 10996 KB Time limit exceeded
14 Execution timed out 10031 ms 10444 KB Time limit exceeded
15 Execution timed out 10029 ms 10452 KB Time limit exceeded
16 Execution timed out 10080 ms 10560 KB Time limit exceeded
17 Execution timed out 10038 ms 10720 KB Time limit exceeded
18 Execution timed out 10042 ms 10692 KB Time limit exceeded
19 Execution timed out 10020 ms 10500 KB Time limit exceeded
20 Execution timed out 10035 ms 12832 KB Time limit exceeded
21 Execution timed out 10038 ms 12660 KB Time limit exceeded
22 Execution timed out 10101 ms 10732 KB Time limit exceeded
23 Execution timed out 10044 ms 11468 KB Time limit exceeded

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10089 ms 12628 KB Time limit exceeded
2 Execution timed out 10047 ms 6488 KB Time limit exceeded
3 Execution timed out 10036 ms 9676 KB Time limit exceeded
4 Execution timed out 10029 ms 6488 KB Time limit exceeded
5 Execution timed out 10098 ms 9948 KB Time limit exceeded
6 Execution timed out 10095 ms 10464 KB Time limit exceeded
7 Execution timed out 10039 ms 10492 KB Time limit exceeded
8 Execution timed out 10019 ms 10328 KB Time limit exceeded
9 Execution timed out 10021 ms 10584 KB Time limit exceeded
10 Execution timed out 10005 ms 10444 KB Time limit exceeded
11 Execution timed out 10041 ms 10460 KB Time limit exceeded
12 Execution timed out 10070 ms 10584 KB Time limit exceeded
13 Execution timed out 10013 ms 10996 KB Time limit exceeded
14 Execution timed out 10031 ms 10444 KB Time limit exceeded
15 Execution timed out 10029 ms 10452 KB Time limit exceeded
16 Execution timed out 10080 ms 10560 KB Time limit exceeded
17 Execution timed out 10038 ms 10720 KB Time limit exceeded
18 Execution timed out 10042 ms 10692 KB Time limit exceeded
19 Execution timed out 10020 ms 10500 KB Time limit exceeded
20 Execution timed out 10035 ms 12832 KB Time limit exceeded
21 Execution timed out 10038 ms 12660 KB Time limit exceeded
22 Execution timed out 10101 ms 10732 KB Time limit exceeded
23 Execution timed out 10044 ms 11468 KB Time limit exceeded

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10089 ms 12628 KB Time limit exceeded
2 Execution timed out 10047 ms 6488 KB Time limit exceeded
3 Execution timed out 10036 ms 9676 KB Time limit exceeded
4 Execution timed out 10029 ms 6488 KB Time limit exceeded
5 Execution timed out 10098 ms 9948 KB Time limit exceeded
6 Execution timed out 10095 ms 10464 KB Time limit exceeded
7 Execution timed out 10039 ms 10492 KB Time limit exceeded
8 Execution timed out 10019 ms 10328 KB Time limit exceeded
9 Execution timed out 10021 ms 10584 KB Time limit exceeded
10 Execution timed out 10005 ms 10444 KB Time limit exceeded
11 Execution timed out 10041 ms 10460 KB Time limit exceeded
12 Execution timed out 10070 ms 10584 KB Time limit exceeded
13 Execution timed out 10013 ms 10996 KB Time limit exceeded
14 Execution timed out 10031 ms 10444 KB Time limit exceeded
15 Execution timed out 10029 ms 10452 KB Time limit exceeded
16 Execution timed out 10080 ms 10560 KB Time limit exceeded
17 Execution timed out 10038 ms 10720 KB Time limit exceeded
18 Execution timed out 10042 ms 10692 KB Time limit exceeded
19 Execution timed out 10020 ms 10500 KB Time limit exceeded
20 Execution timed out 10035 ms 12832 KB Time limit exceeded
21 Execution timed out 10038 ms 12660 KB Time limit exceeded
22 Execution timed out 10101 ms 10732 KB Time limit exceeded
23 Execution timed out 10044 ms 11468 KB Time limit exceeded