oj.uz

Submission #119223

# Submission time Handle Problem Language Result Execution time Memory
119223 2019-06-20T16:56:47 Z patrikpavic2 Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 4 ms 640 KB 
#include "messy.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef vector < int > vi;

const int N = 150;

int n, sol[N];

void dodaj(int l,int r){
	if(l == r) return;
	string s;
	for(int i = 0;i < n;i++){
		if(l <= i && i <= r)
			s.PB('0');
		else
			s.PB('1');
	}
	for(int i = (l + r) / 2 + 1;i <= r;i++){
		s[i] = '1';
		add_element(s);
		s[i] = '0';
	}
	dodaj(l, (l + r) / 2);
	dodaj((l + r) / 2 + 1, r);
	
}	

void rijesi(vi p,int l,int r){
//	cout << l << " " << r << "\n";
//	cout << "P : ";
//	for(int x : p) cout << x << " ";
//	cout << "\n";
	if(l == r){
		sol[p[0]] = l;
		//cout << "gotov\n";
		return;
	}
	string s;
	for(int i = 0;i < n;i++)
		s.PB('1');
	vi L, R;
	for(int x : p)
		s[x] = '0';
//	cout << "tu sam";
	for(int x : p){
		s[x] = '1';
		if(check_element(s))
			R.PB(x);
		else
			L.PB(x);
		s[x] = '0';
	}
//	cout << "tu sam";
	rijesi(L, l, (l + r) / 2);
	rijesi(R, (l + r) / 2 + 1, r);
}

vi restore_permutation(int nn, int w, int r) {
    n = nn;
    vi ret;
    dodaj(0, n - 1);
    //cout << "gotovo dodavanje/n";
   // return vi();
    for(int i = 0;i < n;i++) ret.PB(i);
    compile_set();
    rijesi(ret, 0, n - 1);
    ret.clear();
    for(int i = 0;i < n;i++) ret.PB(sol[i]);
    return ret;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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