oj.uz

Submission #965651

# Submission time Handle Problem Language Result Execution time Memory
965651 2024-04-19T03:37:09 Z fzyzzz_z Saveit (IOI10_saveit) C++17
0 / 100
 349 ms 21780 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] == 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' ? 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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 ms 21424 KB wrong parameter
2 Incorrect 2 ms 11264 KB wrong parameter
3 Incorrect 175 ms 17696 KB wrong parameter
4 Incorrect 2 ms 11264 KB wrong parameter
5 Incorrect 176 ms 17944 KB wrong parameter
6 Incorrect 215 ms 19404 KB wrong parameter
7 Incorrect 220 ms 19720 KB wrong parameter
8 Incorrect 204 ms 18652 KB wrong parameter
9 Incorrect 222 ms 19188 KB wrong parameter
10 Incorrect 225 ms 19160 KB wrong parameter
11 Incorrect 225 ms 19712 KB wrong parameter
12 Incorrect 227 ms 18960 KB wrong parameter
13 Incorrect 236 ms 19312 KB wrong parameter
14 Incorrect 224 ms 19180 KB wrong parameter
15 Incorrect 223 ms 19184 KB wrong parameter
16 Incorrect 232 ms 19784 KB wrong parameter
17 Incorrect 232 ms 19276 KB wrong parameter
18 Incorrect 233 ms 19524 KB wrong parameter
19 Incorrect 225 ms 19460 KB wrong parameter
20 Incorrect 239 ms 21780 KB wrong parameter
21 Incorrect 238 ms 21436 KB wrong parameter
22 Incorrect 220 ms 19716 KB wrong parameter
23 Incorrect 248 ms 21400 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 ms 21424 KB wrong parameter
2 Incorrect 2 ms 11264 KB wrong parameter
3 Incorrect 175 ms 17696 KB wrong parameter
4 Incorrect 2 ms 11264 KB wrong parameter
5 Incorrect 176 ms 17944 KB wrong parameter
6 Incorrect 215 ms 19404 KB wrong parameter
7 Incorrect 220 ms 19720 KB wrong parameter
8 Incorrect 204 ms 18652 KB wrong parameter
9 Incorrect 222 ms 19188 KB wrong parameter
10 Incorrect 225 ms 19160 KB wrong parameter
11 Incorrect 225 ms 19712 KB wrong parameter
12 Incorrect 227 ms 18960 KB wrong parameter
13 Incorrect 236 ms 19312 KB wrong parameter
14 Incorrect 224 ms 19180 KB wrong parameter
15 Incorrect 223 ms 19184 KB wrong parameter
16 Incorrect 232 ms 19784 KB wrong parameter
17 Incorrect 232 ms 19276 KB wrong parameter
18 Incorrect 233 ms 19524 KB wrong parameter
19 Incorrect 225 ms 19460 KB wrong parameter
20 Incorrect 239 ms 21780 KB wrong parameter
21 Incorrect 238 ms 21436 KB wrong parameter
22 Incorrect 220 ms 19716 KB wrong parameter
23 Incorrect 248 ms 21400 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 ms 21424 KB wrong parameter
2 Incorrect 2 ms 11264 KB wrong parameter
3 Incorrect 175 ms 17696 KB wrong parameter
4 Incorrect 2 ms 11264 KB wrong parameter
5 Incorrect 176 ms 17944 KB wrong parameter
6 Incorrect 215 ms 19404 KB wrong parameter
7 Incorrect 220 ms 19720 KB wrong parameter
8 Incorrect 204 ms 18652 KB wrong parameter
9 Incorrect 222 ms 19188 KB wrong parameter
10 Incorrect 225 ms 19160 KB wrong parameter
11 Incorrect 225 ms 19712 KB wrong parameter
12 Incorrect 227 ms 18960 KB wrong parameter
13 Incorrect 236 ms 19312 KB wrong parameter
14 Incorrect 224 ms 19180 KB wrong parameter
15 Incorrect 223 ms 19184 KB wrong parameter
16 Incorrect 232 ms 19784 KB wrong parameter
17 Incorrect 232 ms 19276 KB wrong parameter
18 Incorrect 233 ms 19524 KB wrong parameter
19 Incorrect 225 ms 19460 KB wrong parameter
20 Incorrect 239 ms 21780 KB wrong parameter
21 Incorrect 238 ms 21436 KB wrong parameter
22 Incorrect 220 ms 19716 KB wrong parameter
23 Incorrect 248 ms 21400 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 ms 21424 KB wrong parameter
2 Incorrect 2 ms 11264 KB wrong parameter
3 Incorrect 175 ms 17696 KB wrong parameter
4 Incorrect 2 ms 11264 KB wrong parameter
5 Incorrect 176 ms 17944 KB wrong parameter
6 Incorrect 215 ms 19404 KB wrong parameter
7 Incorrect 220 ms 19720 KB wrong parameter
8 Incorrect 204 ms 18652 KB wrong parameter
9 Incorrect 222 ms 19188 KB wrong parameter
10 Incorrect 225 ms 19160 KB wrong parameter
11 Incorrect 225 ms 19712 KB wrong parameter
12 Incorrect 227 ms 18960 KB wrong parameter
13 Incorrect 236 ms 19312 KB wrong parameter
14 Incorrect 224 ms 19180 KB wrong parameter
15 Incorrect 223 ms 19184 KB wrong parameter
16 Incorrect 232 ms 19784 KB wrong parameter
17 Incorrect 232 ms 19276 KB wrong parameter
18 Incorrect 233 ms 19524 KB wrong parameter
19 Incorrect 225 ms 19460 KB wrong parameter
20 Incorrect 239 ms 21780 KB wrong parameter
21 Incorrect 238 ms 21436 KB wrong parameter
22 Incorrect 220 ms 19716 KB wrong parameter
23 Incorrect 248 ms 21400 KB wrong parameter