oj.uz

Submission #528512

# Submission time Handle Problem Language Result Execution time Memory
528512 2022-02-20T12:20:04 Z fatemetmhr The Collection Game (BOI21_swaps) C++17
35 / 100
 111 ms 47504 KB 
//    Be name khoda!

// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
//     swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//

#include "swaps.h"
#include <bits/stdc++.h>


using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;

const int maxn5 = 1e6 + 10;
const int maxnt = 1e6 + 10;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x)  x.begin(), x.end()

// schedule(i, j) -> (i > j)
// visit()
// answer(vector)

int n, mxlev = 0;
int anss[maxn5];
int lc[maxn5], rc[maxn5];
int root[maxnt], r1[maxnt], r2[maxnt];
int pt = 0;
int lev[maxnt], ver1[maxn5], ver2[maxn5];
int per[maxn5];
vector <int> ver, out, st[maxnt];
int lim = 5000;

inline void visitt(){
	lim--;
	if(lim < 0) exit(0);
	vector <int> res = visit();
	for(int j = 0; j < res.size(); j++)
		anss[ver1[j]] = anss[ver2[j]] = (res[j] ^ 1);
	pt = 0;
	return;
}

inline void solve(int l, int r, int v){
	mxlev = max(mxlev, lev[v]);
	if(r - l == 1){
		root[v] = r2[v] = l;
		r1[v] = -1;
		return;
	}
	int mid = (l + r) >> 1;
	lev[v * 2] = lev[v * 2 + 1] = lev[v] + 1;
	solve(l, mid, v * 2);
	solve(mid, r, v * 2 + 1);
	return;
}

inline void askk(int a, int b){
	ver1[pt] = a;
	ver2[pt] = b;
	pt++;
	schedule(per[a], per[b]);
	return;
}

inline pair<int, int> make_tree(int u, int v, bool ty = false){
	if(u == -1 || v == -1){
		if(ty)
			return {max(u, v), -1};
		return {-1, max(u, v)};
	}
	pair <int, int> rl = make_tree(lc[u], lc[v], false);
	pair <int, int> rr = make_tree(rc[u], rc[v], true);
	if(anss[u]) swap(u, v);
	lc[u] = rl.fi;
	lc[v] = rl.se;
	rc[u] = rr.fi;
	rc[v] = rr.se;
	return {u, v};
}

inline void sch(int u, int v){
	if(u == -1 || v == -1)
		return;
	askk(u, v);
	sch(lc[u], lc[v]);
	sch(rc[u], rc[v]);
	return;
}

inline void find_output(int r){
	if(r == -1)
		return;
	find_output(lc[r]);
	out.pb(per[r]);
	find_output(rc[r]);
	return;
}

void solve(int N, int V) {
	n = N;
	memset(lc, -1, sizeof lc);
	memset(rc, -1, sizeof rc);
	memset(r1, -1, sizeof r1);
	memset(r2, -1, sizeof r2);
	memset(lev, -1, sizeof lev);
	memset(root, -1, sizeof root);
	for(int i = 0; i < n; i++)
		per[i] = i + 1;
	shuffle(per, per + n, rng);
	
	lev[1] = 0;
	solve(0, n, 1);
	
	for(int i = mxlev; i >= 0; i--){
		ver.clear();
		for(int j = 1; j < maxnt; j++) if(lev[j] == i){
			ver.pb(j);
			st[j].clear();
			if(max(r1[j], r2[j]) == -1){
				r1[j] = root[j * 2];
				r2[j] = root[j * 2 + 1];
			}
			//cout << "ok " << j << ' ' << r1[j] << ' ' << r2[j] << endl;
		}
		
		bool ch = true;
		while(ch){
			//cout << "running " << endl;
			ch = false;
			for(auto v : ver) if(max(r1[v], r2[v]) > -1){
				if(min(r1[v], r2[v]) == -1){
					continue;
				}
				sch(r1[v], r2[v]);
				ch = true;
			}
			
			if(ch) visitt();
				
			for(auto v : ver) if(max(r1[v], r2[v]) > -1){
				if(min(r1[v], r2[v]) == -1){
					st[v].pb(max(r1[v], r2[v]));
					//cout << "* " << v << ' ' << st[v].size() << endl;
					r1[v] = r2[v] = -1;
					continue;
				}
				pair<int, int> r = make_tree(r1[v], r2[v]);
				r1[v] = r.fi; r2[v] = lc[r.se];
				st[v].pb(r.se);
				//cout << "& " << v << ' ' << st[v].size() << endl;
			}
		}
		for(auto v : ver){
			//cout << "aha " << v << ' ' << st[v].back() << ' ' << st[v].size() << endl;
			while(!st[v].empty()){
				int u = st[v].back();
				st[v].pop_back();
				if(st[v].size())
					lc[st[v].back()] = u;
				else
					root[v] = u;
			}
			//cout << root[v] << endl;
		}
	}
	
	
	find_output(root[1]); // remember to get per
	
	answer(out);
}

Compilation message

swaps.cpp: In function 'void visitt()':
swaps.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int j = 0; j < res.size(); j++)
      |                 ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47300 KB Correct
2 Correct 48 ms 47288 KB Correct
3 Correct 65 ms 47312 KB Correct
4 Correct 94 ms 47376 KB Correct
5 Correct 95 ms 47376 KB Correct
6 Correct 101 ms 47376 KB Correct
7 Correct 110 ms 47376 KB Correct
8 Correct 97 ms 47376 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 47296 KB Correct
2 Correct 48 ms 47304 KB Correct
3 Correct 61 ms 47308 KB Correct
4 Correct 97 ms 47376 KB Correct
5 Correct 99 ms 47420 KB Correct
6 Correct 105 ms 47380 KB Correct
7 Correct 102 ms 47376 KB Correct
8 Correct 96 ms 47376 KB Correct
9 Correct 98 ms 47380 KB Correct
10 Correct 96 ms 47376 KB Correct
11 Correct 106 ms 47376 KB Correct
12 Correct 97 ms 47504 KB Correct
13 Correct 93 ms 47484 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 47168 KB Correct
2 Correct 48 ms 47284 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 47168 KB Correct
2 Correct 48 ms 47284 KB Correct
3 Correct 38 ms 47168 KB Correct
4 Correct 48 ms 47304 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47304 KB Correct
2 Correct 47 ms 47288 KB Correct
3 Correct 61 ms 47296 KB Correct
4 Correct 108 ms 47436 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47304 KB Correct
2 Correct 47 ms 47288 KB Correct
3 Correct 61 ms 47296 KB Correct
4 Correct 108 ms 47436 KB Correct
5 Correct 36 ms 47276 KB Correct
6 Correct 47 ms 47304 KB Correct
7 Correct 59 ms 47324 KB Correct
8 Correct 95 ms 47380 KB Correct
9 Correct 99 ms 47488 KB Correct
10 Correct 96 ms 47376 KB Correct
11 Correct 103 ms 47376 KB Correct
12 Correct 108 ms 47428 KB Correct
13 Correct 36 ms 47176 KB Correct
14 Correct 49 ms 47276 KB Correct
15 Correct 60 ms 47324 KB Correct
16 Correct 110 ms 47380 KB Correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 47280 KB Correct
2 Correct 48 ms 47204 KB Correct
3 Correct 62 ms 47312 KB Correct
4 Correct 111 ms 47380 KB Correct
5 Runtime error 74 ms 47480 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 47280 KB Correct
2 Correct 48 ms 47204 KB Correct
3 Correct 62 ms 47312 KB Correct
4 Correct 111 ms 47380 KB Correct
5 Runtime error 74 ms 47480 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47276 KB Correct
2 Correct 48 ms 47284 KB Correct
3 Correct 60 ms 47280 KB Correct
4 Correct 100 ms 47376 KB Correct
5 Runtime error 74 ms 47472 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47276 KB Correct
2 Correct 48 ms 47284 KB Correct
3 Correct 60 ms 47280 KB Correct
4 Correct 100 ms 47376 KB Correct
5 Runtime error 74 ms 47472 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 47276 KB Correct
2 Correct 47 ms 47308 KB Correct
3 Correct 63 ms 47288 KB Correct
4 Correct 103 ms 47376 KB Correct
5 Runtime error 76 ms 47368 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 47276 KB Correct
2 Correct 47 ms 47308 KB Correct
3 Correct 63 ms 47288 KB Correct
4 Correct 103 ms 47376 KB Correct
5 Runtime error 76 ms 47368 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -