oj.uz

Submission #854381

# Submission time Handle Problem Language Result Execution time Memory
854381 2023-09-27T07:24:52 Z mychecksedad The Collection Game (BOI21_swaps) C++17
8 / 100
 27 ms 1416 KB 
// #include <swaps.h>
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'

void schedule(int, int);

vector<int> visit();

void answer(std::vector<int>);

vector<int> B;

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

void solve(int N, int V){
	for(int i = 1; i <= N; ++i) B.pb(i);
	vector<pair<int, int>> rang;
	rang.pb({0, N - 1});
	int mx = N-1;
	while(mx > 0){
		vector<pair<int, int>> v;
		vector<vector<int>> Q(rang.size());
		vector<pair<vector<int>, vector<int>>> u(rang.size());
		vector<int> M;
		for(auto p: rang){
			int m = uniform_int_distribution<int> (p.first, p.second) (rng);
			M.pb(B[m]);
			// cout << p.first << ' ' << p.second << ' ' << B[m] << '\n';
		}

		int c = 0;
		int max_len = 0;
		for(auto p: rang){
			for(int i = p.first; i <= p.second; ++i){
				if(M[c] == B[i]) continue;
				Q[c].pb(B[i]);
				// cout << "q" << i << ' ';
			}
			max_len = max(max_len, p.second - p.first);
			++c;
		}
		mx = max_len;
		for(int i = 0; i < max_len; ++i){
			int c = 0;
			for(auto p: rang){
				if(Q[c].empty()){
					++c;
					continue;
				}
				schedule(M[c], Q[c].back());
				++c;
			}
			c = 0;
			vector<int> res = visit();
			reverse(all(res));
			for(auto p: rang){
				if(Q[c].empty()) {
					++c;
					continue;
				}
				if(!res.back()){
					u[c].first.pb(Q[c].back());
					Q[c].pop_back();
				}else{
					u[c].second.pb(Q[c].back());
					Q[c].pop_back();
				}
				res.pop_back();
				++c;
			}
		}
		c = 0;
		int i = 0;
		for(auto r: u){
			if(r.first.size() > 0) v.pb({i, i + r.first.size() - 1});
			v.pb({i + r.first.size(), i + r.first.size()});
			if(r.second.size() > 0) v.pb({i + r.first.size() + 1, i + r.first.size() + 1 + r.second.size() - 1});
			for(int x: r.first) B[i] = x, i++;
			B[i] = M[c], i++;
			for(int x: r.second) B[i] = x, i++;
			++c;
		}
		// cout << "B:";
		// for(auto x: B) cout << x << ' ';
		// en;

		rang = v;
	}
	answer(B);
}

Compilation message

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:51:13: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   51 |    for(auto p: rang){
      |             ^
swaps.cpp:62:13: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   62 |    for(auto p: rang){
      |             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 452 KB Correct
3 Correct 4 ms 452 KB Correct
4 Correct 13 ms 1204 KB Correct
5 Correct 9 ms 964 KB Correct
6 Correct 9 ms 724 KB Correct
7 Correct 13 ms 1416 KB Correct
8 Correct 10 ms 732 KB Correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 700 KB Correct
3 Correct 6 ms 708 KB Correct
4 Correct 10 ms 712 KB Correct
5 Correct 9 ms 492 KB Correct
6 Correct 10 ms 524 KB Correct
7 Correct 11 ms 716 KB Correct
8 Correct 9 ms 704 KB Correct
9 Runtime error 4 ms 452 KB Execution killed with signal 13
10 Halted 0 ms 0 KB -

Subtask #3-1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 24 ms 732 KB Correct

Subtask #3-2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 24 ms 732 KB Correct
3 Incorrect 0 ms 344 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #4-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 22 ms 1132 KB Correct
3 Runtime error 22 ms 684 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 22 ms 1132 KB Correct
3 Runtime error 22 ms 684 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 23 ms 608 KB Correct
3 Runtime error 20 ms 448 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 23 ms 608 KB Correct
3 Runtime error 20 ms 448 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #6-1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 27 ms 1108 KB Correct
3 Runtime error 24 ms 680 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #6-2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 27 ms 1108 KB Correct
3 Runtime error 24 ms 680 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 25 ms 952 KB Correct
3 Runtime error 20 ms 696 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #7-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 25 ms 952 KB Correct
3 Runtime error 20 ms 696 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -