oj.uz

Submission #71396

# Submission time Handle Problem Language Result Execution time Memory
71396 2018-08-24T13:14:48 Z hamzqq9 Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 4 ms 512 KB 
#include "messy.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 2000000000
#define MOD 1000000007
#define N 55
#define MAX 10000006
#define LOG 30
#define KOK 200
using namespace std;

int n;

void find(int bas,int son,vector<int> match,vector<int>& p) {

	string wask(n,'1');

	if(bas+1==son) {

		wask[match[1]]='0';

		if(check_element(wask)) {

			p[match[0]]=bas;
			p[match[1]]=son;

		}
		else {

			p[match[1]]=bas;
			p[match[0]]=son;

		}

		return ;

	}

	for(int i:match) wask[i]='0';

	vector<int> lmatch,rmatch;

	for(int i=0;i<sz(match);i++) {

		wask[match[i]]='1';

		if(check_element(wask)) {

			lmatch.pb(match[i]);

		}
		else {

			rmatch.pb(match[i]);

		}

		wask[match[i]]='0';

	}

	find(bas,orta,lmatch,p);
	find(orta+1,son,rmatch,p);

}

void add(int bas,int son) {

	if(bas==son) return ;

	string wadd(n,'1');

	for(int i=bas;i<=son;i++) wadd[i]='0';

	for(int i=bas;i<=orta;i++) {

		wadd[i]='1';

		add_element(wadd);

		wadd[i]='0';

	}

	add(bas,orta);
	add(orta+1,son);

}

vector<int> restore_permutation(int n, int w, int r) {

	::n=n;

	add(0,n-1);

	compile_set();

	vector<int> match,p(n);

	for(int i=0;i<n;i++) match.pb(i);

	find(0,n-1,match,p);

	return p;

}

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 256 KB n = 8
6 Correct 2 ms 256 KB n = 8
7 Correct 2 ms 384 KB n = 8
8 Correct 2 ms 384 KB n = 8
9 Correct 2 ms 256 KB n = 8
10 Correct 2 ms 384 KB n = 8
11 Correct 3 ms 384 KB n = 8
12 Correct 2 ms 384 KB n = 8
13 Correct 2 ms 356 KB n = 8
14 Correct 2 ms 384 KB n = 8
15 Correct 2 ms 384 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 384 KB n = 32
3 Correct 2 ms 384 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 256 KB n = 32
8 Correct 2 ms 384 KB n = 32
9 Correct 2 ms 256 KB n = 32
10 Correct 2 ms 384 KB n = 32
11 Correct 2 ms 384 KB n = 32
12 Correct 2 ms 256 KB n = 32
13 Correct 2 ms 384 KB n = 32
14 Correct 2 ms 384 KB n = 32
15 Correct 2 ms 384 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 32
2 Correct 2 ms 384 KB n = 32
3 Correct 2 ms 384 KB n = 32
4 Correct 3 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 384 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 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 512 KB n = 128
11 Correct 3 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

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 2 ms 484 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 512 KB n = 128
11 Correct 3 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