oj.uz

Submission #138991

# Submission time Handle Problem Language Result Execution time Memory
138991 2019-07-31T06:46:39 Z ckodser Mechanical Doll (IOI18_doll) C++14
100 / 100
 209 ms 26180 KB 
#include "doll.h"
#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=6e5+500;
const ll inf=1e9+900;
const ll mod=1e9+7;


ll cnt=-2;
ll Woutx[maxn];
ll Wouty[maxn];
		
void Wbild(ll node,vector<ll> a){
	if(a.size()%2==1){
		a.pb(node);
		for(ll i=a.size()-2;i>=0;i--){
			swap(a[i],a[i+1]);
		}
	}
	if(a.size()==2){
		Woutx[-node]=a[0];
		Wouty[-node]=a[1];
		return;
	}
	Woutx[-node]=cnt--;
	Wouty[-node]=cnt--;
	vector<ll> l,r;
	for(ll i=0;i<a.size();i++){
		if(i&1){
			r.pb(a[i]);
		}else{
			l.pb(a[i]);
		}
	}
	Wbild(Woutx[-node],l);
	Wbild(Wouty[-node],r);
}
vector<ll> Wkoj[maxn];
bool vis[maxn];
void solve2(int m,vector<int> a){
	a.pb(0);
	ll n=a.size();
	vector<ll> c,x,y;
	c.resize(m+1);
	if(n==17){
		vector<ll> b;
		for(ll i=1;i<n;i++)b.pb(a[i]);
		fill(c.begin(),c.end(),-1);
		c[0]=a[0];
		Wbild(-1,b);
	}else{
		Wkoj[0].pb(a[0]);
		for(ll i=0;i+1<n;i++){
			Wkoj[a[i]].pb(a[i+1]);
		}
		for(ll i=0;i<n;i++){
			ll v=a[i];
			if(Wkoj[v].size()==1){
				c[v]=Wkoj[v][0];
			}else{
				if(c[v]==0){
					c[v]=cnt--;
				}
			}
		}
		for(ll i=0;i<n;i++){
			ll v=a[i];
			if(!vis[v]){
				vis[v]=1;
				if(Wkoj[v].size()>1){
					Wbild(c[v],Wkoj[v]);
				}
			}
		}
	}
	for(ll i=-1;i>cnt;i--){
		x.pb(Woutx[-i]);
		y.pb(Wouty[-i]);
	}/*
	for(auto v:c)cout<<v<<' ';
	cout<<endl;
	for(auto v:x)cout<<v<<' ';
	cout<<endl;
	for(auto v:y)cout<<v<<' ';
	cout<<endl;
	*/
	answer(c,x,y);
}


ll outx[maxn];
ll outy[maxn];

bool yeki(vector<ll> vec){
	for(ll i=1;i<vec.size();i++)if(vec[i]!=vec[0])return 0;
	return 1;
}
void bild(ll node,vector<ll> a){
	ll n=a.size();
	if((n&(-n))!=n){
		reverse(a.begin(),a.end());
		while(1){
			a.pb(node);
			n=a.size();
			if((n&(-n))==n)break;
		}
		reverse(a.begin(),a.end());
	}
	vector<ll> l,r;
	for(ll i=0;i<a.size();i++){
		if(i&1){
			r.pb(a[i]);
		}else{
			l.pb(a[i]);
		}
	}
	if(yeki(l)){
		outx[-node]=l[0];
	}else{
		outx[-node]=cnt--;
		bild(outx[-node],l);
	}
	if(yeki(r)){
		outy[-node]=r[0];
	}else{
		outy[-node]=cnt--;
		bild(outy[-node],r);
	}
}
ll rev(ll a,ll v){
	vector<ll> b;
	for(ll i=0;i<30;i++){
		if((1<<i)<v){
			b.pb((a>>i)&1);
		}
	}
	reverse(b.begin(),b.end());
	ll ans=0;
	for(ll i=0;i<b.size();i++){
		ans+=((1<<i)*b[i]);
	}
	return ans;
}
vector<ll> okKon(vector<ll> b){
	ll n=b.size();
	if((n&(-n))==n)return b;
	ll v=n;
	while((v&(-v))!=v)v++;
	ll o=v-n;
	vector<ll> ans;
	ans.resize(v);
	fill(ans.begin(),ans.end(),0);
	for(ll i=0;i<o;i++){
		ans[(rev(i,v))]=-1;
	}
	ll cnt=0;
	for(auto t:b){
		while(ans[cnt]==-1)cnt++;
		ans[cnt]=t;
		cnt++;
	}
	return ans;
}
ll cnT[maxn];

void create_circuit(int m,vector<int> a){
	bool sub=1;
	for(auto t:a){
		cnT[t]++;
	}
	for(ll i=0;i<maxn;i++){
		if(cnT[i]>4)sub=0;
	}
	if(sub){
		solve2(m,a);
		return;
	}
	a.pb(0);
	ll n=a.size();
	vector<ll> c,x,y;
	c.resize(m+1);
	vector<ll> b;
	for(ll i=1;i<n;i++)b.pb(a[i]);
	fill(c.begin(),c.end(),-1);
	c[0]=a[0];
	b=okKon(b);
	bild(-1,b);
	for(ll i=-1;i>cnt;i--){
		x.pb(outx[-i]);
		y.pb(outy[-i]);
	}
	/*
	for(auto v:c)cout<<v<<' ';
	cout<<endl;
	for(auto v:x)cout<<v<<' ';
	cout<<endl;
	for(auto v:y)cout<<v<<' ';
	cout<<endl;
	*/
	answer(c,x,y);
}

Compilation message

doll.cpp: In function 'void Wbild(int, std::vector<int>)':
doll.cpp:38:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(ll i=0;i<a.size();i++){
      |             ~^~~~~~~~~
doll.cpp: In function 'bool yeki(std::vector<int>)':
doll.cpp:105:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(ll i=1;i<vec.size();i++)if(vec[i]!=vec[0])return 0;
      |             ~^~~~~~~~~~~
doll.cpp: In function 'void bild(int, std::vector<int>)':
doll.cpp:120:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for(ll i=0;i<a.size();i++){
      |             ~^~~~~~~~~
doll.cpp: In function 'int rev(int, int)':
doll.cpp:149:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |  for(ll i=0;i<b.size();i++){
      |             ~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14376 KB Output is correct
2 Correct 62 ms 18924 KB Output is correct
3 Correct 40 ms 18412 KB Output is correct
4 Correct 12 ms 14412 KB Output is correct
5 Correct 29 ms 15564 KB Output is correct
6 Correct 62 ms 20304 KB Output is correct
7 Correct 15 ms 14412 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14376 KB Output is correct
2 Correct 62 ms 18924 KB Output is correct
3 Correct 40 ms 18412 KB Output is correct
4 Correct 12 ms 14412 KB Output is correct
5 Correct 29 ms 15564 KB Output is correct
6 Correct 62 ms 20304 KB Output is correct
7 Correct 15 ms 14412 KB Output is correct
8 Correct 90 ms 21448 KB Output is correct
9 Correct 105 ms 21760 KB Output is correct
10 Correct 103 ms 25392 KB Output is correct
11 Correct 10 ms 14412 KB Output is correct
12 Correct 10 ms 14412 KB Output is correct
13 Correct 10 ms 14412 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14376 KB Output is correct
2 Correct 62 ms 18924 KB Output is correct
3 Correct 40 ms 18412 KB Output is correct
4 Correct 12 ms 14412 KB Output is correct
5 Correct 29 ms 15564 KB Output is correct
6 Correct 62 ms 20304 KB Output is correct
7 Correct 15 ms 14412 KB Output is correct
8 Correct 90 ms 21448 KB Output is correct
9 Correct 105 ms 21760 KB Output is correct
10 Correct 103 ms 25392 KB Output is correct
11 Correct 10 ms 14412 KB Output is correct
12 Correct 10 ms 14412 KB Output is correct
13 Correct 10 ms 14412 KB Output is correct
14 Correct 180 ms 26180 KB Output is correct
15 Correct 102 ms 21132 KB Output is correct
16 Correct 124 ms 23860 KB Output is correct
17 Correct 13 ms 14408 KB Output is correct
18 Correct 10 ms 14324 KB Output is correct
19 Correct 14 ms 14432 KB Output is correct
20 Correct 124 ms 25216 KB Output is correct
21 Correct 11 ms 14432 KB Output is correct
22 Correct 13 ms 14408 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14348 KB Output is correct
2 Correct 14 ms 14412 KB Output is correct
3 Correct 12 ms 14432 KB Output is correct
4 Correct 12 ms 14416 KB Output is correct
5 Correct 11 ms 14412 KB Output is correct
6 Correct 11 ms 14412 KB Output is correct
7 Correct 11 ms 14412 KB Output is correct
8 Correct 11 ms 14412 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 41 ms 17984 KB Output is correct
3 Correct 91 ms 20576 KB Output is correct
4 Correct 94 ms 21052 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 41 ms 17984 KB Output is correct
3 Correct 91 ms 20576 KB Output is correct
4 Correct 94 ms 21052 KB Output is correct
5 Correct 174 ms 25416 KB Output is correct
6 Correct 165 ms 25252 KB Output is correct
7 Correct 171 ms 25296 KB Output is correct
8 Correct 170 ms 25084 KB Output is correct
9 Correct 132 ms 21216 KB Output is correct
10 Correct 196 ms 24340 KB Output is correct
11 Correct 209 ms 24680 KB Output is correct
12 Correct 203 ms 21572 KB Output is correct
13 Correct 111 ms 21844 KB Output is correct
14 Correct 185 ms 22436 KB Output is correct
15 Correct 174 ms 22460 KB Output is correct
16 Correct 19 ms 14668 KB Output is correct
17 Correct 110 ms 21528 KB Output is correct
18 Correct 105 ms 21440 KB Output is correct
19 Correct 158 ms 21588 KB Output is correct
20 Correct 157 ms 24928 KB Output is correct
21 Correct 187 ms 24616 KB Output is correct
22 Correct 203 ms 24684 KB Output is correct