oj.uz

Submission #406355

# Submission time Handle Problem Language Result Execution time Memory
406355 2021-05-17T12:52:06 Z Kevin_Zhang_TW Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 3 ms 460 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

#include "messy.h"

const int MAX_N = 128;
int n;
string to_s(vector<int> a) {
	string w(n, '0');
	for (int i : a) w[i] = '1';
	return w;
}
vector<int> operator + (vector<int> a, int b) { a.pb(b); return a; }
vector<int> operator + (vector<int> a, const vector<int> &b) { a.insert(end(a), AI(b)); return a; }

void gen_element(int l, int r, vector<int> all = {}) {
	if (l == r) return;
	int m = l + r >> 1;
	for (int i = l;i <= m;++i) {
		add_element(to_s(all + i));
	}
	for (int i = l;i <= m;++i)
		all.pb(i);
	gen_element(m+1, r, all);
	for (int i = l;i <= m;++i) all.pop_back();
	for (int i = m+1;i <= r;++i)
		all.pb(i);
	gen_element(l, m, all);
}
vector<int> rec_element(vector<int> item, vector<int> all = {}) {
	if (item.size() == 1) return item;
	vector<int> L, R;
	for (int i : item)
		(check_element(to_s(all + i)) ? L : R).pb(i);

	vector<int> lall = all + R, rall = all + L;

	auto A = rec_element(L, lall), B = rec_element(R, rall);

	return A + B;
}

std::vector<int> restore_permutation(int n, int w, int r) {
	static int cnt;
	assert(++cnt == 1);
	::n = n;
	gen_element(0, n-1);
    compile_set();
	vector<int> ids(n); iota(AI(ids), 0);
	vector<int> sorted = rec_element(ids);
	vector<int> per(n);
	for (int i = 0;i < n;++i)
		per[ sorted[i] ] = i;
	return per;
}

Compilation message

messy.cpp: In function 'void gen_element(int, int, std::vector<int>)':
messy.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int m = l + r >> 1;
      |          ~~^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 32
2 Correct 1 ms 204 KB n = 32
3 Correct 1 ms 204 KB n = 32
4 Correct 1 ms 204 KB n = 32
5 Correct 1 ms 292 KB n = 32
6 Correct 1 ms 204 KB n = 32
7 Correct 1 ms 204 KB n = 32
8 Correct 1 ms 204 KB n = 32
9 Correct 1 ms 296 KB n = 32
10 Correct 1 ms 296 KB n = 32
11 Correct 1 ms 216 KB n = 32
12 Correct 1 ms 204 KB n = 32
13 Correct 1 ms 292 KB n = 32
14 Correct 1 ms 204 KB n = 32
15 Correct 1 ms 288 KB n = 32

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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