oj.uz

Submission #718040

# Submission time Handle Problem Language Result Execution time Memory
718040 2023-04-03T08:26:49 Z myrcella Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 2 ms 468 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "messy.h"

vector <int> ans;
int N;

void solve(vector<int> pos) {
	if (SZ(pos)==1) return;
	int mid = SZ(pos)>>1;
	string s;
	rep(i,0,N) s+="1";
	for (int v:pos) s[v] = '0';
	vector <int> pl,pr;
	rep(i,0,mid) {
		int v = pos[i];
		s[v] = '1';
		add_element(s);
		s[v] = '0';
		pl.pb(v);
	}
	rep(i,mid,SZ(pos)) pr.pb(pos[i]);
	
	solve(pl);
	solve(pr);
}

void query(vector <int> pos,vector <int> val) {
	if (SZ(pos)==1) {
		ans[val[0]] = pos[0];
		return;
	}
	string q;
	rep(i,0,N) q+="1";
	for (int v:val) q[v] = '0';
	vector <int> vl,vr;
	for (int v:val) {
		q[v] = '1';
		if (check_element(q)) vl.pb(v);
		else vr.pb(v);
		q[v] = '0';
	}
	vector <int> pl,pr;
	rep(i,0,SZ(pos)/2) pl.pb(pos[i]),pr.pb(pos[i+SZ(pos)/2]);
	query(pl,vl),query(pr,vr);
}

std::vector<int> restore_permutation(int n, int w, int r) {
	N=n;
	ans.resize(n);
	vector <int> p,v;
	rep(i,0,n) p.pb(i),v.pb(i);
	solve(p);
	compile_set();
	query(p,v);
    return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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