oj.uz

Submission #145060

# Submission time Handle Problem Language Result Execution time Memory
145060 2019-08-18T15:53:11 Z shashwatchandra Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 4 ms 632 KB 
#include <vector>
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;

#define mid (l+r+1)/2
int N;
string xd = "";
vector<int> ans;

void recurseadd(int l,int r){
	if(l == r)return;
	string cur = xd;
	for(int i = 0;i < l;i++)cur[i] = '1';
	for(int i = r+1;i < N;i++)cur[i] = '1';
	for(int i = l;i < mid;i++){
		cur[i] = '1';
		add_element(cur);
		cur[i] = '0';
	}
	recurseadd(l,mid-1);
	recurseadd(mid,r);
}	

void recurseget(int l,int r,string anc){
	string cur = anc;
	if(l == r){
		for(int i = 0;i <N;i++){
			if(cur[i] == '0')ans[l] = i;
		}
		return;
	}
	string lu = anc;
	string ru = anc;
	for(int i = 0;i < N;i++){
		if(cur[i] == '0'){
			cur[i] = '1';
			if(check_element(cur)){
				lu[i] = '1';
			}
			else{
				ru[i] = '1';
			}
			cur[i] = '0';
		}
	}
	recurseget(l,mid-1,ru);
	recurseget(mid,r,lu);

}

vector<int> restore_permutation(int n, int w, int r) {
	N = n;
	for(int i = 0;i < n;i++)xd += "0";
   	recurseadd(0,n-1);
   	ans.resize(N);
    compile_set();
    recurseget(0,n-1,xd);
    vector<int> pos(n);
    for(int i = 0;i < ans.size();i++)pos[ans[i]] = i;
   	return pos;
}

Compilation message

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:60:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < ans.size();i++)pos[ans[i]] = i;
                   ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 8
2 Correct 2 ms 128 KB n = 8
3 Correct 2 ms 376 KB n = 8
4 Correct 2 ms 376 KB n = 8
5 Correct 2 ms 376 KB n = 8
6 Correct 2 ms 376 KB n = 8
7 Correct 2 ms 348 KB n = 8
8 Correct 2 ms 360 KB n = 8
9 Correct 2 ms 376 KB n = 8
10 Correct 2 ms 376 KB n = 8
11 Correct 2 ms 256 KB n = 8
12 Correct 2 ms 376 KB n = 8
13 Correct 2 ms 292 KB n = 8
14 Correct 2 ms 376 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 3 ms 376 KB n = 32
2 Correct 2 ms 376 KB n = 32
3 Correct 2 ms 376 KB n = 32
4 Correct 2 ms 376 KB n = 32
5 Correct 3 ms 376 KB n = 32
6 Correct 2 ms 376 KB n = 32
7 Correct 2 ms 376 KB n = 32
8 Correct 2 ms 376 KB n = 32
9 Correct 2 ms 376 KB n = 32
10 Correct 3 ms 376 KB n = 32
11 Correct 3 ms 376 KB n = 32
12 Correct 2 ms 380 KB n = 32
13 Correct 2 ms 376 KB n = 32
14 Correct 2 ms 376 KB n = 32
15 Correct 2 ms 356 KB n = 32

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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