oj.uz

Submission #528476

# Submission time Handle Problem Language Result Execution time Memory
528476 2022-02-20T10:53:51 Z fatemetmhr The Collection Game (BOI21_swaps) C++17
35 / 100
 110 ms 47556 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];

inline void visitt(){
	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:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int j = 0; j < res.size(); j++)
      |                 ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47176 KB Correct
2 Correct 45 ms 47300 KB Correct
3 Correct 61 ms 47432 KB Correct
4 Correct 97 ms 47380 KB Correct
5 Correct 92 ms 47376 KB Correct
6 Correct 98 ms 47380 KB Correct
7 Correct 95 ms 47376 KB Correct
8 Correct 96 ms 47376 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47176 KB Correct
2 Correct 46 ms 47168 KB Correct
3 Correct 59 ms 47320 KB Correct
4 Correct 100 ms 47360 KB Correct
5 Correct 94 ms 47384 KB Correct
6 Correct 104 ms 47484 KB Correct
7 Correct 109 ms 47380 KB Correct
8 Correct 98 ms 47372 KB Correct
9 Correct 92 ms 47380 KB Correct
10 Correct 90 ms 47376 KB Correct
11 Correct 109 ms 47376 KB Correct
12 Correct 110 ms 47376 KB Correct
13 Correct 108 ms 47412 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47304 KB Correct
2 Correct 45 ms 47244 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47304 KB Correct
2 Correct 45 ms 47244 KB Correct
3 Correct 34 ms 47296 KB Correct
4 Correct 46 ms 47396 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 47284 KB Correct
2 Correct 44 ms 47292 KB Correct
3 Correct 60 ms 47308 KB Correct
4 Correct 94 ms 47380 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 47284 KB Correct
2 Correct 44 ms 47292 KB Correct
3 Correct 60 ms 47308 KB Correct
4 Correct 94 ms 47380 KB Correct
5 Correct 35 ms 47172 KB Correct
6 Correct 47 ms 47228 KB Correct
7 Correct 61 ms 47308 KB Correct
8 Correct 94 ms 47376 KB Correct
9 Correct 100 ms 47380 KB Correct
10 Correct 95 ms 47376 KB Correct
11 Correct 100 ms 47380 KB Correct
12 Correct 101 ms 47372 KB Correct
13 Correct 38 ms 47280 KB Correct
14 Correct 56 ms 47264 KB Correct
15 Correct 58 ms 47316 KB Correct
16 Correct 104 ms 47384 KB Correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47156 KB Correct
2 Correct 47 ms 47168 KB Correct
3 Correct 62 ms 47312 KB Correct
4 Correct 94 ms 47380 KB Correct
5 Runtime error 94 ms 47380 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 35 ms 47156 KB Correct
2 Correct 47 ms 47168 KB Correct
3 Correct 62 ms 47312 KB Correct
4 Correct 94 ms 47380 KB Correct
5 Runtime error 94 ms 47380 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 39 ms 47208 KB Correct
2 Correct 52 ms 47300 KB Correct
3 Correct 73 ms 47312 KB Correct
4 Correct 100 ms 47500 KB Correct
5 Runtime error 83 ms 47376 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 39 ms 47208 KB Correct
2 Correct 52 ms 47300 KB Correct
3 Correct 73 ms 47312 KB Correct
4 Correct 100 ms 47500 KB Correct
5 Runtime error 83 ms 47376 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 40 ms 47276 KB Correct
2 Correct 49 ms 47292 KB Correct
3 Correct 69 ms 47280 KB Correct
4 Correct 102 ms 47380 KB Correct
5 Runtime error 77 ms 47556 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 40 ms 47276 KB Correct
2 Correct 49 ms 47292 KB Correct
3 Correct 69 ms 47280 KB Correct
4 Correct 102 ms 47380 KB Correct
5 Runtime error 77 ms 47556 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -