oj.uz

Submission #965644

# Submission time Handle Problem Language Result Execution time Memory
965644 2024-04-19T03:31:14 Z fzyzzz_z Saveit (IOI10_saveit) C++17
0 / 100
 10000 ms 12860 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 < 15; ++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 10034 ms 12860 KB Time limit exceeded
2 Execution timed out 10036 ms 6748 KB Time limit exceeded
3 Execution timed out 10058 ms 9676 KB Time limit exceeded
4 Execution timed out 10084 ms 6488 KB Time limit exceeded
5 Execution timed out 10019 ms 9956 KB Time limit exceeded
6 Execution timed out 10016 ms 10972 KB Time limit exceeded
7 Execution timed out 10006 ms 10696 KB Time limit exceeded
8 Execution timed out 10039 ms 10184 KB Time limit exceeded
9 Execution timed out 10048 ms 10448 KB Time limit exceeded
10 Execution timed out 10055 ms 10444 KB Time limit exceeded
11 Execution timed out 10035 ms 10712 KB Time limit exceeded
12 Execution timed out 10057 ms 10584 KB Time limit exceeded
13 Execution timed out 10097 ms 10692 KB Time limit exceeded
14 Execution timed out 10014 ms 10448 KB Time limit exceeded
15 Execution timed out 10016 ms 10452 KB Time limit exceeded
16 Execution timed out 10022 ms 10672 KB Time limit exceeded
17 Execution timed out 10066 ms 10712 KB Time limit exceeded
18 Execution timed out 10093 ms 10556 KB Time limit exceeded
19 Execution timed out 10048 ms 10508 KB Time limit exceeded
20 Execution timed out 10070 ms 12648 KB Time limit exceeded
21 Execution timed out 10088 ms 12740 KB Time limit exceeded
22 Execution timed out 10085 ms 10596 KB Time limit exceeded
23 Execution timed out 10094 ms 12644 KB Time limit exceeded

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10034 ms 12860 KB Time limit exceeded
2 Execution timed out 10036 ms 6748 KB Time limit exceeded
3 Execution timed out 10058 ms 9676 KB Time limit exceeded
4 Execution timed out 10084 ms 6488 KB Time limit exceeded
5 Execution timed out 10019 ms 9956 KB Time limit exceeded
6 Execution timed out 10016 ms 10972 KB Time limit exceeded
7 Execution timed out 10006 ms 10696 KB Time limit exceeded
8 Execution timed out 10039 ms 10184 KB Time limit exceeded
9 Execution timed out 10048 ms 10448 KB Time limit exceeded
10 Execution timed out 10055 ms 10444 KB Time limit exceeded
11 Execution timed out 10035 ms 10712 KB Time limit exceeded
12 Execution timed out 10057 ms 10584 KB Time limit exceeded
13 Execution timed out 10097 ms 10692 KB Time limit exceeded
14 Execution timed out 10014 ms 10448 KB Time limit exceeded
15 Execution timed out 10016 ms 10452 KB Time limit exceeded
16 Execution timed out 10022 ms 10672 KB Time limit exceeded
17 Execution timed out 10066 ms 10712 KB Time limit exceeded
18 Execution timed out 10093 ms 10556 KB Time limit exceeded
19 Execution timed out 10048 ms 10508 KB Time limit exceeded
20 Execution timed out 10070 ms 12648 KB Time limit exceeded
21 Execution timed out 10088 ms 12740 KB Time limit exceeded
22 Execution timed out 10085 ms 10596 KB Time limit exceeded
23 Execution timed out 10094 ms 12644 KB Time limit exceeded

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10034 ms 12860 KB Time limit exceeded
2 Execution timed out 10036 ms 6748 KB Time limit exceeded
3 Execution timed out 10058 ms 9676 KB Time limit exceeded
4 Execution timed out 10084 ms 6488 KB Time limit exceeded
5 Execution timed out 10019 ms 9956 KB Time limit exceeded
6 Execution timed out 10016 ms 10972 KB Time limit exceeded
7 Execution timed out 10006 ms 10696 KB Time limit exceeded
8 Execution timed out 10039 ms 10184 KB Time limit exceeded
9 Execution timed out 10048 ms 10448 KB Time limit exceeded
10 Execution timed out 10055 ms 10444 KB Time limit exceeded
11 Execution timed out 10035 ms 10712 KB Time limit exceeded
12 Execution timed out 10057 ms 10584 KB Time limit exceeded
13 Execution timed out 10097 ms 10692 KB Time limit exceeded
14 Execution timed out 10014 ms 10448 KB Time limit exceeded
15 Execution timed out 10016 ms 10452 KB Time limit exceeded
16 Execution timed out 10022 ms 10672 KB Time limit exceeded
17 Execution timed out 10066 ms 10712 KB Time limit exceeded
18 Execution timed out 10093 ms 10556 KB Time limit exceeded
19 Execution timed out 10048 ms 10508 KB Time limit exceeded
20 Execution timed out 10070 ms 12648 KB Time limit exceeded
21 Execution timed out 10088 ms 12740 KB Time limit exceeded
22 Execution timed out 10085 ms 10596 KB Time limit exceeded
23 Execution timed out 10094 ms 12644 KB Time limit exceeded

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10034 ms 12860 KB Time limit exceeded
2 Execution timed out 10036 ms 6748 KB Time limit exceeded
3 Execution timed out 10058 ms 9676 KB Time limit exceeded
4 Execution timed out 10084 ms 6488 KB Time limit exceeded
5 Execution timed out 10019 ms 9956 KB Time limit exceeded
6 Execution timed out 10016 ms 10972 KB Time limit exceeded
7 Execution timed out 10006 ms 10696 KB Time limit exceeded
8 Execution timed out 10039 ms 10184 KB Time limit exceeded
9 Execution timed out 10048 ms 10448 KB Time limit exceeded
10 Execution timed out 10055 ms 10444 KB Time limit exceeded
11 Execution timed out 10035 ms 10712 KB Time limit exceeded
12 Execution timed out 10057 ms 10584 KB Time limit exceeded
13 Execution timed out 10097 ms 10692 KB Time limit exceeded
14 Execution timed out 10014 ms 10448 KB Time limit exceeded
15 Execution timed out 10016 ms 10452 KB Time limit exceeded
16 Execution timed out 10022 ms 10672 KB Time limit exceeded
17 Execution timed out 10066 ms 10712 KB Time limit exceeded
18 Execution timed out 10093 ms 10556 KB Time limit exceeded
19 Execution timed out 10048 ms 10508 KB Time limit exceeded
20 Execution timed out 10070 ms 12648 KB Time limit exceeded
21 Execution timed out 10088 ms 12740 KB Time limit exceeded
22 Execution timed out 10085 ms 10596 KB Time limit exceeded
23 Execution timed out 10094 ms 12644 KB Time limit exceeded