oj.uz

Submission #992568

# Submission time Handle Problem Language Result Execution time Memory
992568 2024-06-04T17:11:07 Z vqpahmad Magic Show (APIO24_show) C++17
100 / 100
 267 ms 195804 KB 
#include<bits/stdc++.h>
#include "Alice.h"
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 5000;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
struct DSU {
	int p[MAXN], s[MAXN];
	void init(){
		for (int i = 0; i < MAXN; i++){
			p[i] = i;
			s[i] = 1;
		}
	}
	int find(int u){
		if (p[u] == u) return u;
		return p[u] = find(p[u]);
	}
	void merge(int u, int v){
		u = find(u);
		v = find(v);
		if (s[u] < s[v]) swap(u, v);
		s[u] += s[v];
		p[v] = u;
		return;
	}
} dsu;

int edges[MAXN][MAXN];
vector<pair<int,int>> Alice(){
	srand(14);
	for (int i = 0; i < 5000; i++){
		for (int j = i + 1; j < 5000; j++){
			edges[i][j] = rand() % 60;
			edges[j][i] = edges[i][j];
		}
	}
	long long x = setN(5000);
	vector<pii> ans;
	dsu.init();
	set<int> st;
	while (sz(ans) < 4999){
		int u = rand() % 5000, v = rand() % 5000;
		bool flag = 1;
		for (int i = u; i < u + 5000 && flag; i++){
			for (int j = v; j < v + 5000 && flag; j++){
				int U = i % 5000, V = j % 5000;
				if (U == V) continue;
				if (dsu.find(U) != dsu.find(V) && ((x >> edges[U][V]) & 1)){
					st.insert(edges[U][V]);
					dsu.merge(U, V);
					ans.pb({U, V});
					flag = 0;
				}
			}
		}
	}
	for (int i = 0; i < sz(ans); i++){
		if (ans[i].F > ans[i].S) swap(ans[i].F, ans[i].S);
	}
	sort(all(ans));
	for (int i = 0; i < sz(ans); i++){
		ans[i].F++;
		ans[i].S++;
	}
	return ans;
}
#include<bits/stdc++.h>
#include "Bob.h"
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().

int edges2[5001][5001];
long long Bob(std::vector<std::pair<int,int>> V){
	srand(14);
	for (int i = 0; i < 5000; i++){
		for (int j = i + 1; j < 5000; j++){
			edges2[i][j] = rand() % 60;
		}
	}
	ll ans = 0;
	set<int> st;
	for (auto [u, v] : V){
		st.insert(edges2[u - 1][v - 1]);
		ans |= (1ll << edges2[u - 1][v - 1]);
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 195544 KB Correct.
2 Correct 226 ms 195488 KB Correct.
3 Correct 244 ms 195616 KB Correct.
4 Correct 227 ms 195540 KB Correct.
5 Correct 257 ms 195540 KB Correct.
6 Correct 222 ms 195584 KB Correct.
7 Correct 226 ms 195540 KB Correct.
8 Correct 235 ms 195540 KB Correct.
9 Correct 236 ms 195804 KB Correct.
10 Correct 232 ms 195540 KB Correct.
11 Correct 239 ms 195640 KB Correct.
12 Correct 228 ms 195592 KB Correct.

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 195544 KB Correct.
2 Correct 226 ms 195488 KB Correct.
3 Correct 244 ms 195616 KB Correct.
4 Correct 227 ms 195540 KB Correct.
5 Correct 257 ms 195540 KB Correct.
6 Correct 222 ms 195584 KB Correct.
7 Correct 226 ms 195540 KB Correct.
8 Correct 235 ms 195540 KB Correct.
9 Correct 236 ms 195804 KB Correct.
10 Correct 232 ms 195540 KB Correct.
11 Correct 239 ms 195640 KB Correct.
12 Correct 228 ms 195592 KB Correct.
13 Correct 224 ms 195580 KB Correct.
14 Correct 228 ms 195488 KB Correct.
15 Correct 226 ms 195540 KB Correct.
16 Correct 222 ms 195660 KB Correct.
17 Correct 240 ms 195496 KB Correct.
18 Correct 235 ms 195468 KB Correct.
19 Correct 225 ms 195420 KB Correct.
20 Correct 225 ms 195524 KB Correct.
21 Correct 244 ms 195540 KB Correct.
22 Correct 249 ms 195544 KB Correct.
23 Correct 234 ms 195624 KB Correct.
24 Correct 232 ms 195628 KB Correct.

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 195544 KB Correct.
2 Correct 226 ms 195488 KB Correct.
3 Correct 244 ms 195616 KB Correct.
4 Correct 227 ms 195540 KB Correct.
5 Correct 257 ms 195540 KB Correct.
6 Correct 222 ms 195584 KB Correct.
7 Correct 226 ms 195540 KB Correct.
8 Correct 235 ms 195540 KB Correct.
9 Correct 236 ms 195804 KB Correct.
10 Correct 232 ms 195540 KB Correct.
11 Correct 239 ms 195640 KB Correct.
12 Correct 228 ms 195592 KB Correct.
13 Correct 224 ms 195580 KB Correct.
14 Correct 228 ms 195488 KB Correct.
15 Correct 226 ms 195540 KB Correct.
16 Correct 222 ms 195660 KB Correct.
17 Correct 240 ms 195496 KB Correct.
18 Correct 235 ms 195468 KB Correct.
19 Correct 225 ms 195420 KB Correct.
20 Correct 225 ms 195524 KB Correct.
21 Correct 244 ms 195540 KB Correct.
22 Correct 249 ms 195544 KB Correct.
23 Correct 234 ms 195624 KB Correct.
24 Correct 232 ms 195628 KB Correct.
25 Correct 231 ms 195628 KB Correct.
26 Correct 228 ms 195568 KB Correct.
27 Correct 226 ms 195600 KB Correct.
28 Correct 222 ms 195528 KB Correct.
29 Correct 225 ms 195628 KB Correct.
30 Correct 222 ms 195540 KB Correct.
31 Correct 230 ms 195516 KB Correct.
32 Correct 248 ms 195632 KB Correct.
33 Correct 267 ms 195588 KB Correct.
34 Correct 224 ms 195612 KB Correct.
35 Correct 223 ms 195352 KB Correct.
36 Correct 227 ms 195540 KB Correct.
37 Correct 225 ms 195536 KB Correct.
38 Correct 220 ms 195544 KB Correct.
39 Correct 226 ms 195644 KB Correct.
40 Correct 251 ms 195480 KB Correct.
41 Correct 222 ms 195368 KB Correct.
42 Correct 224 ms 195664 KB Correct.
43 Correct 222 ms 195540 KB Correct.
44 Correct 226 ms 195456 KB Correct.