oj.uz

Submission #952557

# Submission time Handle Problem Language Result Execution time Memory
952557 2024-03-24T08:46:17 Z SmuggingSpun Unscrambling a Messy Bug (IOI16_messy) C++14
89 / 100
 2 ms 760 KB 
#include "messy.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int>restore_permutation(int n, int w, int r){
	if(n <= 32){
		string s(n, '0'), current(n, '0');
		for(int i = 0; i + 1 < n; i++){
			s[i] = '1';
			add_element(s);
		}
		compile_set();
		vector<int>ans(n), p(n);
		iota(p.begin(), p.end(), 0);
		for(int i = 0; i < n; i++){
			shuffle(p.begin(), p.end(), rng);
			int index = int(p.size()) - 1;
			for(int i = 0; i + 1 < p.size(); i++){
				current[p[i]] = '1';
				if(check_element(current)){
					index = i;
					break;
				}
				current[p[i]] = '0';
			}
			current[p[index]] = '1';
			ans[p[index]] = i;
			p.erase(p.begin() + index);
		}
		return ans;
	}
	function<void(int, int, vector<int>)>add;
	add = [&] (int l, int r, vector<int>must_1){
		if(l == r){
			return;
		}	
		int m = (l + r) >> 1;
		string s(n, '0');
		for(int& x : must_1){
			s[x] = '1';
		}
		for(int i = l; i <= m; i++){
			s[i] = '1';
			add_element(s);
			s[i] = '0';
			must_1.emplace_back(i);
		}
		add(m + 1, r, must_1);
		for(int i = l; i <= m; i++){
			must_1.pop_back();
		}
		for(int i = m + 1; i <= r; i++){
			must_1.emplace_back(i);
		}
		add(l, m, must_1);
	};
	add(0, n - 1, vector<int>());
	compile_set();
	vector<int>ans(n);
	function<void(int, int, vector<int>, vector<int>)>solve;
	solve = [&] (int l, int r, vector<int>index, vector<int>must_1){
		if(l == r){
			ans[index[0]] = l;
			return;
		}
		string s(n, '0');
		for(int& x : must_1){
			s[x] = '1';
		}
		int m = (l + r) >> 1;
		vector<int>left, right;
		for(int i = 0; i < index.size(); i++){
			s[index[i]] = '1';
			if(check_element(s)){
				left.emplace_back(index[i]);
			}
			else{
				right.emplace_back(index[i]);
			}
			s[index[i]] = '0';
		}
		for(int& x : left){
			must_1.emplace_back(x);
		}
		solve(m + 1, r, right, must_1);
		for(int i = 0; i < left.size(); i++){
			must_1.pop_back();
		}
		for(int& x : right){
			must_1.emplace_back(x);
		}
		solve(l, m, left, must_1);
	};
	vector<int>index(n);
	iota(index.begin(), index.end(), 0);
	solve(0, n - 1, index, vector<int>());
	return ans;
}

Compilation message

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:18:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |    for(int i = 0; i + 1 < p.size(); i++){
      |                   ~~~~~~^~~~~~~~~~
messy.cpp: In lambda function:
messy.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i = 0; i < index.size(); i++){
      |                  ~~^~~~~~~~~~~~~~
messy.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i = 0; i < left.size(); i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 8
2 Correct 0 ms 600 KB n = 8
3 Correct 1 ms 348 KB n = 8
4 Correct 0 ms 348 KB n = 8
5 Correct 0 ms 348 KB n = 8
6 Correct 0 ms 348 KB n = 8
7 Correct 1 ms 348 KB n = 8
8 Correct 1 ms 348 KB n = 8
9 Correct 1 ms 348 KB n = 8
10 Correct 0 ms 348 KB n = 8
11 Correct 0 ms 348 KB n = 8
12 Correct 0 ms 348 KB n = 8
13 Correct 0 ms 348 KB n = 8
14 Correct 0 ms 348 KB n = 8
15 Correct 1 ms 348 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 32
2 Correct 1 ms 600 KB n = 32
3 Correct 0 ms 348 KB n = 32
4 Correct 0 ms 348 KB n = 32
5 Correct 1 ms 348 KB n = 32
6 Correct 1 ms 348 KB n = 32
7 Correct 0 ms 348 KB n = 32
8 Correct 0 ms 348 KB n = 32
9 Correct 0 ms 348 KB n = 32
10 Correct 0 ms 348 KB n = 32
11 Correct 0 ms 344 KB n = 32
12 Correct 0 ms 348 KB n = 32
13 Correct 0 ms 348 KB n = 32
14 Correct 0 ms 348 KB n = 32
15 Correct 0 ms 344 KB n = 32

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 32
2 Correct 0 ms 348 KB n = 32
3 Correct 0 ms 348 KB n = 32
4 Correct 0 ms 348 KB n = 32
5 Correct 1 ms 348 KB n = 32
6 Correct 0 ms 348 KB n = 32
7 Correct 1 ms 440 KB n = 32
8 Correct 1 ms 600 KB n = 32
9 Correct 0 ms 348 KB n = 32
10 Correct 0 ms 348 KB n = 32
11 Correct 0 ms 348 KB n = 32
12 Correct 1 ms 348 KB n = 32
13 Correct 0 ms 348 KB n = 32
14 Incorrect 1 ms 348 KB grader returned WA
15 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB n = 128
2 Correct 1 ms 604 KB n = 128
3 Correct 1 ms 604 KB n = 128
4 Correct 1 ms 604 KB n = 128
5 Correct 1 ms 600 KB n = 128
6 Correct 1 ms 600 KB n = 128
7 Correct 1 ms 604 KB n = 128
8 Correct 1 ms 604 KB n = 128
9 Correct 1 ms 600 KB n = 128
10 Correct 2 ms 760 KB n = 128
11 Correct 1 ms 604 KB n = 128
12 Correct 1 ms 600 KB n = 128
13 Correct 1 ms 604 KB n = 128
14 Correct 1 ms 600 KB n = 128
15 Correct 1 ms 604 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB n = 128
2 Correct 1 ms 604 KB n = 128
3 Correct 1 ms 604 KB n = 128
4 Correct 1 ms 556 KB n = 128
5 Correct 1 ms 604 KB n = 128
6 Correct 1 ms 604 KB n = 128
7 Correct 2 ms 600 KB n = 128
8 Correct 1 ms 600 KB n = 128
9 Correct 1 ms 604 KB n = 128
10 Correct 2 ms 604 KB n = 128
11 Correct 1 ms 604 KB n = 128
12 Correct 1 ms 604 KB n = 128
13 Correct 1 ms 604 KB n = 128
14 Correct 1 ms 556 KB n = 128
15 Correct 2 ms 604 KB n = 128