oj.uz

Submission #528479

# Submission time Handle Problem Language Result Execution time Memory
528479 2022-02-20T10:56:32 Z fatemetmhr The Collection Game (BOI21_swaps) C++17
35 / 100
 109 ms 47560 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 35 ms 47268 KB Correct
2 Correct 47 ms 47304 KB Correct
3 Correct 61 ms 47444 KB Correct
4 Correct 89 ms 47380 KB Correct
5 Correct 89 ms 47372 KB Correct
6 Correct 94 ms 47492 KB Correct
7 Correct 93 ms 47376 KB Correct
8 Correct 91 ms 47372 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47280 KB Correct
2 Correct 48 ms 47296 KB Correct
3 Correct 64 ms 47324 KB Correct
4 Correct 100 ms 47372 KB Correct
5 Correct 97 ms 47376 KB Correct
6 Correct 99 ms 47448 KB Correct
7 Correct 105 ms 47376 KB Correct
8 Correct 95 ms 47380 KB Correct
9 Correct 105 ms 47380 KB Correct
10 Correct 109 ms 47376 KB Correct
11 Correct 107 ms 47372 KB Correct
12 Correct 108 ms 47408 KB Correct
13 Correct 89 ms 47380 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47212 KB Correct
2 Correct 47 ms 47196 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47212 KB Correct
2 Correct 47 ms 47196 KB Correct
3 Correct 38 ms 47276 KB Correct
4 Correct 48 ms 47280 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47204 KB Correct
2 Correct 43 ms 47292 KB Correct
3 Correct 61 ms 47296 KB Correct
4 Correct 97 ms 47380 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47204 KB Correct
2 Correct 43 ms 47292 KB Correct
3 Correct 61 ms 47296 KB Correct
4 Correct 97 ms 47380 KB Correct
5 Correct 39 ms 47168 KB Correct
6 Correct 46 ms 47356 KB Correct
7 Correct 59 ms 47320 KB Correct
8 Correct 100 ms 47380 KB Correct
9 Correct 106 ms 47376 KB Correct
10 Correct 92 ms 47380 KB Correct
11 Correct 109 ms 47372 KB Correct
12 Correct 109 ms 47560 KB Correct
13 Correct 34 ms 47176 KB Correct
14 Correct 49 ms 47300 KB Correct
15 Correct 79 ms 47304 KB Correct
16 Correct 99 ms 47380 KB Correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47280 KB Correct
2 Correct 46 ms 47284 KB Correct
3 Correct 72 ms 47304 KB Correct
4 Correct 94 ms 47376 KB Correct
5 Runtime error 74 ms 47456 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 36 ms 47280 KB Correct
2 Correct 46 ms 47284 KB Correct
3 Correct 72 ms 47304 KB Correct
4 Correct 94 ms 47376 KB Correct
5 Runtime error 74 ms 47456 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 34 ms 47272 KB Correct
2 Correct 48 ms 47292 KB Correct
3 Correct 60 ms 47324 KB Correct
4 Correct 94 ms 47376 KB Correct
5 Runtime error 75 ms 47360 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 34 ms 47272 KB Correct
2 Correct 48 ms 47292 KB Correct
3 Correct 60 ms 47324 KB Correct
4 Correct 94 ms 47376 KB Correct
5 Runtime error 75 ms 47360 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 38 ms 47176 KB Correct
2 Correct 47 ms 47268 KB Correct
3 Correct 61 ms 47320 KB Correct
4 Correct 99 ms 47500 KB Correct
5 Runtime error 97 ms 47384 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 38 ms 47176 KB Correct
2 Correct 47 ms 47268 KB Correct
3 Correct 61 ms 47320 KB Correct
4 Correct 99 ms 47500 KB Correct
5 Runtime error 97 ms 47384 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -