oj.uz

Submission #965650

# Submission time Handle Problem Language Result Execution time Memory
965650 2024-04-19T03:36:14 Z fzyzzz_z Saveit (IOI10_saveit) C++17
0 / 100
 340 ms 19784 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'); 
 
 
	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 340 ms 16668 KB wrong parameter
2 Incorrect 3 ms 4620 KB wrong parameter
3 Incorrect 177 ms 11300 KB wrong parameter
4 Incorrect 3 ms 4624 KB wrong parameter
5 Incorrect 178 ms 11860 KB wrong parameter
6 Incorrect 230 ms 13344 KB wrong parameter
7 Incorrect 228 ms 13540 KB wrong parameter
8 Incorrect 204 ms 12160 KB wrong parameter
9 Incorrect 224 ms 12944 KB wrong parameter
10 Incorrect 222 ms 13196 KB wrong parameter
11 Incorrect 224 ms 12772 KB wrong parameter
12 Incorrect 228 ms 15020 KB wrong parameter
13 Incorrect 240 ms 19784 KB wrong parameter
14 Incorrect 226 ms 14732 KB wrong parameter
15 Incorrect 227 ms 13216 KB wrong parameter
16 Incorrect 240 ms 15076 KB wrong parameter
17 Incorrect 237 ms 17356 KB wrong parameter
18 Incorrect 241 ms 13592 KB wrong parameter
19 Incorrect 227 ms 15376 KB wrong parameter
20 Incorrect 247 ms 13056 KB wrong parameter
21 Incorrect 248 ms 13280 KB wrong parameter
22 Incorrect 241 ms 13432 KB wrong parameter
23 Incorrect 258 ms 13716 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 340 ms 16668 KB wrong parameter
2 Incorrect 3 ms 4620 KB wrong parameter
3 Incorrect 177 ms 11300 KB wrong parameter
4 Incorrect 3 ms 4624 KB wrong parameter
5 Incorrect 178 ms 11860 KB wrong parameter
6 Incorrect 230 ms 13344 KB wrong parameter
7 Incorrect 228 ms 13540 KB wrong parameter
8 Incorrect 204 ms 12160 KB wrong parameter
9 Incorrect 224 ms 12944 KB wrong parameter
10 Incorrect 222 ms 13196 KB wrong parameter
11 Incorrect 224 ms 12772 KB wrong parameter
12 Incorrect 228 ms 15020 KB wrong parameter
13 Incorrect 240 ms 19784 KB wrong parameter
14 Incorrect 226 ms 14732 KB wrong parameter
15 Incorrect 227 ms 13216 KB wrong parameter
16 Incorrect 240 ms 15076 KB wrong parameter
17 Incorrect 237 ms 17356 KB wrong parameter
18 Incorrect 241 ms 13592 KB wrong parameter
19 Incorrect 227 ms 15376 KB wrong parameter
20 Incorrect 247 ms 13056 KB wrong parameter
21 Incorrect 248 ms 13280 KB wrong parameter
22 Incorrect 241 ms 13432 KB wrong parameter
23 Incorrect 258 ms 13716 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 340 ms 16668 KB wrong parameter
2 Incorrect 3 ms 4620 KB wrong parameter
3 Incorrect 177 ms 11300 KB wrong parameter
4 Incorrect 3 ms 4624 KB wrong parameter
5 Incorrect 178 ms 11860 KB wrong parameter
6 Incorrect 230 ms 13344 KB wrong parameter
7 Incorrect 228 ms 13540 KB wrong parameter
8 Incorrect 204 ms 12160 KB wrong parameter
9 Incorrect 224 ms 12944 KB wrong parameter
10 Incorrect 222 ms 13196 KB wrong parameter
11 Incorrect 224 ms 12772 KB wrong parameter
12 Incorrect 228 ms 15020 KB wrong parameter
13 Incorrect 240 ms 19784 KB wrong parameter
14 Incorrect 226 ms 14732 KB wrong parameter
15 Incorrect 227 ms 13216 KB wrong parameter
16 Incorrect 240 ms 15076 KB wrong parameter
17 Incorrect 237 ms 17356 KB wrong parameter
18 Incorrect 241 ms 13592 KB wrong parameter
19 Incorrect 227 ms 15376 KB wrong parameter
20 Incorrect 247 ms 13056 KB wrong parameter
21 Incorrect 248 ms 13280 KB wrong parameter
22 Incorrect 241 ms 13432 KB wrong parameter
23 Incorrect 258 ms 13716 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 340 ms 16668 KB wrong parameter
2 Incorrect 3 ms 4620 KB wrong parameter
3 Incorrect 177 ms 11300 KB wrong parameter
4 Incorrect 3 ms 4624 KB wrong parameter
5 Incorrect 178 ms 11860 KB wrong parameter
6 Incorrect 230 ms 13344 KB wrong parameter
7 Incorrect 228 ms 13540 KB wrong parameter
8 Incorrect 204 ms 12160 KB wrong parameter
9 Incorrect 224 ms 12944 KB wrong parameter
10 Incorrect 222 ms 13196 KB wrong parameter
11 Incorrect 224 ms 12772 KB wrong parameter
12 Incorrect 228 ms 15020 KB wrong parameter
13 Incorrect 240 ms 19784 KB wrong parameter
14 Incorrect 226 ms 14732 KB wrong parameter
15 Incorrect 227 ms 13216 KB wrong parameter
16 Incorrect 240 ms 15076 KB wrong parameter
17 Incorrect 237 ms 17356 KB wrong parameter
18 Incorrect 241 ms 13592 KB wrong parameter
19 Incorrect 227 ms 15376 KB wrong parameter
20 Incorrect 247 ms 13056 KB wrong parameter
21 Incorrect 248 ms 13280 KB wrong parameter
22 Incorrect 241 ms 13432 KB wrong parameter
23 Incorrect 258 ms 13716 KB wrong parameter