oj.uz

Submission #415272

# Submission time Handle Problem Language Result Execution time Memory
415272 2021-05-31T19:00:58 Z cfalas Mechanical Doll (IOI18_doll) C++14
100 / 100
 521 ms 29812 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)

int s=0, n;
vector<vi> nxt;
vector<int> C, X, Y;
vi pr;

int b;
int inv(int x){
	vi a;
	//cout<<x<<" ";
	FOR(i,b) a.push_back(x%2), x/=2;
	ll ans=0;
	FOA(v,a) ans*=2, ans+=v;
	//cout<<ans<<endl;
	return ans;
}

vi rep;

ii cnt(int x, int l, int r){
	set<int> all;
	if((1<<b)-r > (int)nxt[x].size()) return {1,C[x]};
	return {2,0};
}

void rec(int x, int l, int r){
	//cout<<x<<": "<<l<<" "<<r<<endl;
	if(l==r) return;
	if(r==l+1){
		//cout<<l<<" "<<r<<" "<<cnt(x,l,r).F<<endl;
		assert(cnt(x,l,r).F!=1);

		assert(pr.size()==nxt[x].size());
		if((1<<b)-l <= (int)nxt[x].size()) X.push_back(nxt[x][pr[pr.size() - (1<<b) + l]]);
		else X.push_back(C[x]);
		
		l++;
		assert(l<=(1<<b));
		if((1<<b)-l <= (int)nxt[x].size()) Y.push_back(nxt[x][pr[pr.size() - (1<<b) + l]]);
		else Y.push_back(C[x]);
	}
	else{
		ii p = cnt(x,l,MID);

		int q = Y.size();
		Y.push_back(s);

		if(p.F==1) X.push_back(p.S);
		else{
			X.push_back(-(++s));
			rec(x, l, MID);
		}
		p = cnt(x,MID+1,r);
		//cout<<MID+1<<" "<<r<<" "<<p.F<<endl;
		if(p.F==1) Y[q] = (p.S);
		else {
			Y[q] = -(++s);
			rec(x, MID+1,r);
		}
	}
}

void create_circuit(int M, std::vector<int> A) {
	n = A.size();
	nxt.assign(M+1, vi());
	C.assign(M+1, 0);

	FOR(i,n) nxt[0].push_back(A[i]);
	nxt[0].push_back(0);

	FOR(i,M+1){
		C[i] = -1;
	}
	s = 0;
	FOR(x,1){
		int q = nxt[x].size();
		if(q==0) continue;
		else if(nxt[x].size()==1) C[x] = nxt[x][0];
		else{
			int t = q-1;

			int l=0;
			while(t) l++, t/=2;
			b = l;
			//cout<<q<<": "<<b<<endl;

			// generate permutation
			pr.clear();
			FORi(i,(1<<b)-nxt[x].size(),(1<<b)) pr.push_back(inv(i));
			set<int> all;
			map<int, int> ordered;
			int cnt=0;
			FOA(v,pr) all.insert(v);
			FOA(v,all) ordered[v] = cnt++;;
			FOR(i,pr.size()) pr[i] = ordered[pr[i]];
#ifdef LOCAL
			cout<<x<<": ";
			FOA(v,pr) cout<<v<<" ";
			cout<<endl;
#endif

			C[x] = -(++s);
			rec(x, 0, (1<<l)-1);
		}
	}
#ifdef LOCAL
	FOA(v,C) cout<<v<<" ";
	cout<<endl;
	FOA(v,X) cout<<v<<" ";
	cout<<endl;
	FOA(v,Y) cout<<v<<" ";
	cout<<endl;
#endif

	answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 119 ms 11948 KB Output is correct
3 Correct 107 ms 10960 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 3788 KB Output is correct
6 Correct 198 ms 16228 KB Output is correct
7 Correct 2 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 119 ms 11948 KB Output is correct
3 Correct 107 ms 10960 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 3788 KB Output is correct
6 Correct 198 ms 16228 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 234 ms 19100 KB Output is correct
9 Correct 239 ms 20152 KB Output is correct
10 Correct 493 ms 29812 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 119 ms 11948 KB Output is correct
3 Correct 107 ms 10960 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 3788 KB Output is correct
6 Correct 198 ms 16228 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 234 ms 19100 KB Output is correct
9 Correct 239 ms 20152 KB Output is correct
10 Correct 493 ms 29812 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 493 ms 28444 KB Output is correct
15 Correct 239 ms 17992 KB Output is correct
16 Correct 415 ms 28196 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 429 ms 28644 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 236 ms 17444 KB Output is correct
3 Correct 221 ms 17320 KB Output is correct
4 Correct 405 ms 26024 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 236 ms 17444 KB Output is correct
3 Correct 221 ms 17320 KB Output is correct
4 Correct 405 ms 26024 KB Output is correct
5 Correct 521 ms 27988 KB Output is correct
6 Correct 396 ms 26808 KB Output is correct
7 Correct 510 ms 27564 KB Output is correct
8 Correct 461 ms 26744 KB Output is correct
9 Correct 307 ms 17084 KB Output is correct
10 Correct 501 ms 26568 KB Output is correct
11 Correct 519 ms 26132 KB Output is correct
12 Correct 223 ms 17376 KB Output is correct
13 Correct 204 ms 17696 KB Output is correct
14 Correct 240 ms 17964 KB Output is correct
15 Correct 242 ms 18080 KB Output is correct
16 Correct 7 ms 844 KB Output is correct
17 Correct 205 ms 16752 KB Output is correct
18 Correct 198 ms 17360 KB Output is correct
19 Correct 262 ms 17340 KB Output is correct
20 Correct 499 ms 26228 KB Output is correct
21 Correct 397 ms 26300 KB Output is correct
22 Correct 464 ms 26308 KB Output is correct