oj.uz

답안 #1072739

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1072739 2024-08-24T03:48:13 Z Faisal_Saqib 자동 인형 (IOI18_doll) C++17
16 / 100
 144 ms 40756 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define vll vector<int>
#define ll int
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
vector<int> XP,YP;
const int NM=1e6+10;
ll cp[NM],label=0,father_of_all=-1;
vll fast_order(ll n)
{
    if(n==2)
        return {1,2};
    vll ans;
    ll hn=n/2;
    for(int i=1;i<=n;i+=2)
        ans.pb(i);
    vll hans(hn);
    vll np=fast_order(n/2);
    for(int j=0;j<hn;j++)
        hans[np[j]-1]=ans[j];
    ans.clear();
    for(auto i:hans)
        ans.pb(i);
    for(auto i:hans)
        ans.pb(i+1);
    return ans;
}
vll childx,childy,order_,npp;
int label_it(vll&p,int l,int r,bool lp=0)
{
	if((l-r)==0){
		if(p[l]==-NM)
		{
			return father_of_all;
		}
		return p[l];
	}
	int mid=(l+r)/2;
	bool use=0;
	for(int i=l;i<=r;i++)
	{
		if(p[i]!=-NM)
		{
			use=1;
			break;
		}
	}
	label++;
	int usep=-label;
	int fk=-1;
	if(!use)
	{
		fk=childx.size();
		childx.pb(father_of_all);
		childy.pb(father_of_all);
	}
	else
	{
		int lc=label_it(p,l,mid,1);
		int rc=label_it(p,mid+1,r,1);
		fk=childx.size();
		childx.pb(lc);
		childy.pb(rc);
	}
	order_.pb(fk);
	npp.pb(usep);
	return usep;
}
vll child_[NM];
ll fake_id=0,state[NM],req_sz=0;
int label_it_fake(vll&p,int l,int r,bool lp=0)
{
	if((l-r)==0){
		if(p[l]==-NM)
			return 0;
		req_sz++;
		return -l-1; // always negative
	}
	int mid=(l+r)/2;
	bool use=0;
	for(int i=l;i<=r;i++)
	{
		if(p[i]!=-NM)
		{
			use=1;
			break;
		}
	}
	int fk=fake_id;
	fake_id++;
	child_[fk].clear();
	state[fk]=0;
	if(!use)
	{
		child_[fk].pb(0);
		child_[fk].pb(0);
	}
	else
	{
		int lc=label_it_fake(p,l,mid,1);
		int rc=label_it_fake(p,mid+1,r,1);
		child_[fk].pb(lc);
		child_[fk].pb(rc);
	}
	return fk;
}
vll my_order;
void generate_order(int cur)
{
	if(my_order.size()==req_sz)return;
	if(cur<0)
	{
		my_order.push_back(cur);
		generate_order(0);
		return;
	}
	state[cur]=1-state[cur];
	generate_order(child_[cur][1-state[cur]]);
}
bool check(int m,vector<int> a)
{
	map<int,int> cnt;
	int mx=0;
	for(auto i:a)
	{
		cnt[i]++;
		mx=max(mx,cnt[i]);
	}
	return (mx<=4);
}
void subtask(int m, std::vector<int> a)
{
	vector<int> ans(m+1);
	vector<int> child[m+2];
	vector<int> cur;
	cur.pb(0);
	for(int j=0;j<a.size();j++)
		cur.pb(a[j]);
	cur.pb(0);
	for(int j=1;j<cur.size();j++)
		child[cur[j-1]].push_back(cur[j]);
	vector<int> x,y;
	int s=0;
	for(int i=0;i<=m;i++)
	{
		if(child[i].size()==1)
		{
			ans[i]=child[i][0];
		}
		else if(child[i].size()==2) // solve atmost 2
		{
			// We need
			s++;
			ans[i]=-s;
			x.pb(child[i][0]);
			y.pb(child[i][1]);
		}
		else if(child[i].size()==3)
		{
			int s1=s+1;
			int s2=s+2;
			int s3=s+3;
			s+=3;
			ans[i]=-s1;
			// s1
				x.pb(-s2);
				y.pb(-s3);
			//s2
				x.pb(-s1);
				y.pb(child[i][1]);
			//s3
				x.pb(child[i][0]);
				y.pb(child[i][2]);
		}
		else if(child[i].size()==4)
		{
			int s1=s+1;
			int s2=s+2;
			int s3=s+3;
			s+=3;
			ans[i]=-s1;
			// s1
				x.pb(-s2);
				y.pb(-s3);
			//s2
				x.pb(child[i][0]);
				y.pb(child[i][2]);
			//s3
				x.pb(child[i][1]);
				y.pb(child[i][3]);
		}
	}
	// for(int i=0;i<=m;i++)
	// {
	// 	cout<<ans[i]<<' ';
	// }
	// cout<<endl;
	// for(int i=0;i<s;i++)
	// {
	// 	cout<<x[i]<<' '<<y[i]<<endl;
	// }
	answer(ans,x,y);
}
// int make_(vector<int> a)
// {

// }
void create_circuit(int m, std::vector<int> a)
{
	if(check(m,a))
	{
		subtask(m,a);
		return;
	}
	a.pb(0);
	XP.clear();
	YP.clear();
	label=0;
	vector<int> ans(m+1);
	vector<int> child[m+2];
	vector<int> cur;
	int last=0;
	int pointer_=0;
	int my_sz=a.size();
	for(int szp=0;szp<18;szp++)
	{
		if(my_sz&(1<<szp))
		{
			int sz=(1<<szp);
			for(int j=0;j<sz;j++)
				child[last].push_back(a[pointer_++]);
			last=a[pointer_-1];
		}
	}
	for(int i=0;i<=m;i++)
	{
		if(child[i].size()==0)continue;
		if(child[i].size()==1)
		{
			ans[i]=child[i][0];
		}
		else
		{
			ll pw=1;
			while(child[i].size()>pw)
				pw*=2;
			int zxp=child[i].size();
			vll fl(pw);
			int cpp=0;
			for(int j=zxp;j<pw;j++)
				fl[cpp]=-NM,cpp++;
			for(int j=0;j<zxp;j++)
				fl[cpp]=child[i][j],cpp++;
			father_of_all=-label-1;
			for(auto ele:child[i])
				ans[ele]=father_of_all;
			childx.clear();
			childy.clear();
			order_.clear();
			npp.clear();
			ll og=label;
			req_sz=0;
			my_order.clear();
			fake_id=0;
			int root=label_it_fake(fl,0,pw-1);
			generate_order(root);
			for(int i=0;i<pw;i++)fl[i]=-NM;
			for(int k=0;k<child[i].size();k++)
			{
				fl[-my_order[k]-1]=child[i][k];
			}
			label_it(fl,0,pw-1);
			ll last=XP.size();
			for(int i=0;i<order_.size();i++)
			{
				XP.pb(0);
				YP.pb(0);
			}
			for(int i=0;i<order_.size();i++)
			{
				ll cur=-og-npp[i]-1;
				XP[last+cur]=(childx[i]);
				YP[last+cur]=(childy[i]);
			}
			ans[i]=father_of_all;
		}
	}
	answer(ans,XP,YP);
	/*}

	else
	{
		cur.pb(0);
		for(int j=0;j<a.size();j++)
			cur.pb(a[j]);
		cur.pb(0);
		for(int j=1;j<cur.size();j++)
			child[cur[j-1]].push_back(cur[j]);
		for(int i=0;i<=m;i++)
		{
			if(child[i].size()==0)continue;
			if(child[i].size()==1)
			{
				ans[i]=child[i][0];
			}
			else
			{
				ll pw=1;
				while(child[i].size()>pw)
					pw*=2;
				int zxp=child[i].size();
				vll fl(pw);
				int cpp=0;
				for(int j=zxp;j<pw;j++)
					fl[cpp]=-NM,cpp++;
				for(int j=0;j<zxp;j++)
					fl[cpp]=child[i][j],cpp++;
				father_of_all=-label-1;
				childx.clear();
				childy.clear();
				order_.clear();
				npp.clear();
				ll og=label;
				father_of_all=-label-1;
				childx.clear();
				childy.clear();
				order_.clear();
				npp.clear();
				req_sz=0;
				my_order.clear();
				fake_id=0;
				int root=label_it_fake(fl,0,pw-1);
				generate_order(root);
				for(int i=0;i<pw;i++)fl[i]=-NM;
				for(int k=0;k<child[i].size();k++)
				{
					fl[-my_order[k]-1]=child[i][k];
				}
				label_it(fl,0,pw-1);
				ll last=XP.size();
				for(int i=0;i<order_.size();i++)
				{
					XP.pb(0);
					YP.pb(0);
				}
				for(int i=0;i<order_.size();i++)
				{
					ll cur=-og-npp[i]-1;
					XP[last+cur]=(childx[i]);
					YP[last+cur]=(childy[i]);
				}
				ans[i]=father_of_all;
			}
		}
		answer(ans,XP,YP);
	}
	*/
}

Compilation message

doll.cpp: In function 'void generate_order(int)':
doll.cpp:111:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |  if(my_order.size()==req_sz)return;
      |     ~~~~~~~~~~~~~~~^~~~~~~~
doll.cpp: In function 'void subtask(int, std::vector<int>)':
doll.cpp:138:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |  for(int j=0;j<a.size();j++)
      |              ~^~~~~~~~~
doll.cpp:141:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |  for(int j=1;j<cur.size();j++)
      |              ~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:246:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  246 |    while(child[i].size()>pw)
      |          ~~~~~~~~~~~~~~~^~~
doll.cpp:269:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  269 |    for(int k=0;k<child[i].size();k++)
      |                ~^~~~~~~~~~~~~~~~
doll.cpp:275:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  275 |    for(int i=0;i<order_.size();i++)
      |                ~^~~~~~~~~~~~~~
doll.cpp:280:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  280 |    for(int i=0;i<order_.size();i++)
      |                ~^~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 25436 KB Output is correct
2 Correct 49 ms 32652 KB Output is correct
3 Correct 49 ms 31264 KB Output is correct
4 Correct 11 ms 25436 KB Output is correct
5 Correct 16 ms 28924 KB Output is correct
6 Correct 70 ms 34572 KB Output is correct
7 Correct 10 ms 25428 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 25436 KB Output is correct
2 Correct 49 ms 32652 KB Output is correct
3 Correct 49 ms 31264 KB Output is correct
4 Correct 11 ms 25436 KB Output is correct
5 Correct 16 ms 28924 KB Output is correct
6 Correct 70 ms 34572 KB Output is correct
7 Correct 10 ms 25428 KB Output is correct
8 Correct 77 ms 34628 KB Output is correct
9 Correct 89 ms 36584 KB Output is correct
10 Correct 129 ms 40756 KB Output is correct
11 Correct 9 ms 25432 KB Output is correct
12 Correct 12 ms 25432 KB Output is correct
13 Correct 10 ms 25436 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 25436 KB Output is correct
2 Correct 49 ms 32652 KB Output is correct
3 Correct 49 ms 31264 KB Output is correct
4 Correct 11 ms 25436 KB Output is correct
5 Correct 16 ms 28924 KB Output is correct
6 Correct 70 ms 34572 KB Output is correct
7 Correct 10 ms 25428 KB Output is correct
8 Correct 77 ms 34628 KB Output is correct
9 Correct 89 ms 36584 KB Output is correct
10 Correct 129 ms 40756 KB Output is correct
11 Correct 9 ms 25432 KB Output is correct
12 Correct 12 ms 25432 KB Output is correct
13 Correct 10 ms 25436 KB Output is correct
14 Correct 142 ms 39168 KB Output is correct
15 Correct 78 ms 33348 KB Output is correct
16 Correct 105 ms 36672 KB Output is correct
17 Correct 11 ms 25180 KB Output is correct
18 Correct 10 ms 25432 KB Output is correct
19 Correct 10 ms 25436 KB Output is correct
20 Correct 144 ms 39096 KB Output is correct
21 Correct 11 ms 25436 KB Output is correct
22 Correct 11 ms 25180 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 25180 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 25436 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 25436 KB wrong motion
2 Halted 0 ms 0 KB -