oj.uz

Submission #138886

# Submission time Handle Problem Language Result Execution time Memory
138886 2019-07-30T18:04:01 Z arthurconmy Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 5 ms 508 KB 
#include <bits/stdc++.h>
#include "messy.h"
 
using namespace std;
 
vector<int> restore_permutation(int n, int w, int r) 
{
	for(int no_groups=2; no_groups<=n; no_groups*=2)
	{
		for(int g=0; g<no_groups; g+=2)
		{
			for(int i=0; i<int(n/no_groups); i++)
			{
				string S = "";
 
				for(int d=1; d <= g*int(n/no_groups); d++) S+='1';
				for(int d=1; d <= i; d++) S+='0';
 
				S+='1';
 
				for(int d=1; d < int(n/no_groups) - i; d++) S+='0';
				for(int d=1; d <= int(n/no_groups); d++) S+='0';
 
				while(int(S.size())<n) S+='1';
 
				add_element(S);
			}
		}
	}
 
	compile_set();
 
	vector<vector<int>> group(4*n); // kinda like a segment tree (indexing) I guess
 
	for(int i=0; i<n; i++) group[1].push_back(i); // initially we know fuck all about everything
 
	for(int no_groups=1; no_groups<n; no_groups*=2) // this is the number of groups we have at this stage
	{
		for(int g=0; g<no_groups; g++)
		{
			string S="";
 
			for(int i=0; i<n; i++) S+='0';
 
			for(int i=no_groups; i<no_groups*2; i++)
			{
				if(i != no_groups+g)
				{
					for(auto u:group[i]) S[u]='1';
				}
			}
 
			for(auto u:group[no_groups+g])
			{
				string S2 = S;
				S2[u]='1';
 
				if(check_element(S2))
				{
					group[2*(no_groups+g)].push_back(u);
				}
 
				else
				{
					group[2*(no_groups+g) + 1].push_back(u);
				}
			}
		}
	}
 
	vector<int> ans(n);
 
	for(int i=n; i<n+n; i++)
	{
		ans[group[i][0]]=i-n;
	}
 
	return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 8
2 Correct 2 ms 256 KB n = 8
3 Correct 2 ms 256 KB n = 8
4 Correct 2 ms 256 KB n = 8
5 Correct 2 ms 376 KB n = 8
6 Correct 2 ms 256 KB n = 8
7 Correct 2 ms 256 KB n = 8
8 Correct 2 ms 376 KB n = 8
9 Correct 2 ms 376 KB n = 8
10 Correct 3 ms 376 KB n = 8
11 Correct 2 ms 256 KB n = 8
12 Correct 2 ms 252 KB n = 8
13 Correct 2 ms 256 KB n = 8
14 Correct 2 ms 256 KB n = 8
15 Correct 2 ms 376 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 3 ms 376 KB n = 32
3 Correct 2 ms 376 KB n = 32
4 Correct 3 ms 376 KB n = 32
5 Correct 2 ms 252 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 1 ms 376 KB n = 32
11 Correct 2 ms 376 KB n = 32
12 Correct 2 ms 376 KB n = 32
13 Correct 2 ms 396 KB n = 32
14 Correct 2 ms 376 KB n = 32
15 Correct 2 ms 376 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 360 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 376 KB n = 32
11 Correct 2 ms 376 KB n = 32
12 Correct 2 ms 376 KB n = 32
13 Correct 4 ms 376 KB n = 32
14 Correct 4 ms 376 KB n = 32
15 Correct 3 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 504 KB n = 128
3 Correct 4 ms 508 KB n = 128
4 Correct 4 ms 504 KB n = 128
5 Correct 5 ms 504 KB n = 128
6 Correct 5 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 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 504 KB n = 128
14 Correct 4 ms 504 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 504 KB n = 128
4 Correct 4 ms 504 KB n = 128
5 Correct 5 ms 504 KB n = 128
6 Correct 4 ms 504 KB n = 128
7 Correct 4 ms 476 KB n = 128
8 Correct 3 ms 504 KB n = 128
9 Correct 4 ms 504 KB n = 128
10 Correct 4 ms 504 KB n = 128
11 Correct 4 ms 488 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 504 KB n = 128