제출 #138991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138991		ckodser	자동 인형 (IOI18_doll)	C++14	100 / 100	209 ms	26180 KiB

doll

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56