oj.uz

답안 #1072255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1072255 2024-08-23T16:04:20 Z Faisal_Saqib 자동 인형 (IOI18_doll) C++17
86.6719 / 100
 237 ms 101404 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)
{
	// cout<<"Range "<<l<<' '<<r<<' '<<" p: ";
	// for(int i=l;i<=r;i++)
	// {
	// 	cout<<p[i]<<' ';
	// }
	// cout<<endl;
	if((l-r)==0){
		if(p[l]==-NM)
			return 0;
		req_sz++;
		// cout<<"Label: "<<-l-1<<endl;
		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)
	{
		// all minus one is subtree
		// cout<<"Node "<<fk<<endl;
		// cout<<"Child: "<<0<<' '<<0<<endl;
		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);
		// cout<<"Node "<<fk<<endl;
		// cout<<"Child: "<<lc<<' '<<rc<<endl;
		// cout<<"Range "<<l<<' '<<r<<endl;
		// cout<<"Child: "<<XP.back()<<' '<<YP.back()<<endl;
	}
	// cout<<"Assigned to range "<<l<<' '<<r<<' ';
	// cout<<fk<<endl;
	return fk;
}
vll my_order;
void generate_order(int cur)
{
	if(my_order.size()==req_sz)return;
	// cout<<"At "<<cur<<endl;
	if(cur<0)
	{
		// cout<<"Pushing "<<cur<<endl;
		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);
}
void create_circuit(int m, std::vector<int> a)
{
	if(check(m,a))
	{
		subtask(m,a);
		return;
	}
	XP.clear();
	YP.clear();
	label=0;
	vector<int> ans(m+1);
	vector<int> child[m+2];
	vector<int> cur;
	{
		int v=a[0];
		child[0].push_back(v);
		for(int j=1;j<a.size();j++)
			child[v].push_back(a[j]);
		child[v].push_back(0);
		int lps=0;
		for(int j=0;j<=m;j++)
			ans[j]=-1;
		// cout<<"SZ: "<<child[v].size()<<endl;
		for(auto i:{0,v})
		{
			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);
				for(int j=0;j<zxp;j++)
					fl[j]=child[i][j];
				for(int j=zxp;j<pw;j++)
					fl[j]=-NM;
				if(fl[zxp-1]==0)
					swap(fl[zxp-1],fl[pw-1]);
				// cout<<"After\n";
				// for(int j=0;j<pw;j++)
				// {
					// cout<<fl[j]<<' ';
				// }
				// cout<<endl;
				father_of_all=-label-1;
				childx.clear();
				childy.clear();
				order_.clear();
				npp.clear();
				ll og=label;
				father_of_all=-label-1;
				// pw then
				// cout<<"Father "<<father_of_all<<endl;
				// cout<<"Do label\n";
				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);
				// cout<<"Made the fake tree\n";
				// for(int j=0;j<fake_id;j++)
				// {
					// cout<<"Had node "<<j<<endl;
					// cout<<"Adj: ";
					// for(auto k:child_[j])
					// {
						// cout<<k<<' ';
					// }
					// cout<<endl;
				// }
				generate_order(root);
				// cout<<"My Order: ";
				// for(auto j:my_order)
					// cout<<j<<' ';
				// cout<<endl;
				// cout<<"Req order: ";
				// for(auto j:child[i])
				// {
					// cout<<j<<' ';
				// }
				// cout<<endl;
				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];
				}
				// cout<<"Before\n";
				// for(int i=0;i<pw;i++)
				// {
					// cout<<fl[i]<<' ';
				// }
				// cout<<endl;
				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;
			}
		}
		// cout<<"ans\n";
		// for(int i=0;i<=m;i++)
		// {
		// 	cout<<i<<' '<<ans[i]<<' '<<'Z'<<endl;;
		// }
		// cout<<endl;
		// cout<<"xy\n";
		// cout<<XP.size()<<endl;
		// cout<<YP.size()<<endl;
		// for(auto i:XP)
		// {
		// 	cout<<i<<' ';
		// }
		// cout<<endl;
		// for(auto i:YP)
		// {
		// 	cout<<i<<' ';
		// }
		// cout<<endl;
		// for(int i=0;i<label;i++)
		// {
		// 	cout<<-i-1<<' '<<XP[i]<<' '<<'X'<<endl;
		// 	cout<<-i-1<<' '<<YP[i]<<' '<<'Y'<<endl;
		// 	// cout<<XP[i]<<' '<<YP[i]<<endl;
		// }
		answer(ans,XP,YP);
	}
}

Compilation message

doll.cpp: In function 'void generate_order(int)':
doll.cpp:127:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |  if(my_order.size()==req_sz)return;
      |     ~~~~~~~~~~~~~~~^~~~~~~~
doll.cpp: In function 'void subtask(int, std::vector<int>)':
doll.cpp:156:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |  for(int j=0;j<a.size();j++)
      |              ~^~~~~~~~~
doll.cpp:159:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |  for(int j=1;j<cur.size();j++)
      |              ~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:239:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |   for(int j=1;j<a.size();j++)
      |               ~^~~~~~~~~
doll.cpp:256:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  256 |     while(child[i].size()>pw)
      |           ~~~~~~~~~~~~~~~^~~
doll.cpp:313:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  313 |     for(int k=0;k<child[i].size();k++)
      |                 ~^~~~~~~~~~~~~~~~
doll.cpp:325:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  325 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:330:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  330 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:242:7: warning: unused variable 'lps' [-Wunused-variable]
  242 |   int lps=0;
      |       ^~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 49 ms 31144 KB Output is correct
3 Correct 47 ms 29724 KB Output is correct
4 Correct 10 ms 23896 KB Output is correct
5 Correct 18 ms 27224 KB Output is correct
6 Correct 82 ms 33120 KB Output is correct
7 Correct 10 ms 23896 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 49 ms 31144 KB Output is correct
3 Correct 47 ms 29724 KB Output is correct
4 Correct 10 ms 23896 KB Output is correct
5 Correct 18 ms 27224 KB Output is correct
6 Correct 82 ms 33120 KB Output is correct
7 Correct 10 ms 23896 KB Output is correct
8 Correct 74 ms 33100 KB Output is correct
9 Correct 82 ms 35092 KB Output is correct
10 Correct 115 ms 39220 KB Output is correct
11 Correct 10 ms 23896 KB Output is correct
12 Correct 9 ms 23944 KB Output is correct
13 Correct 9 ms 23896 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 49 ms 31144 KB Output is correct
3 Correct 47 ms 29724 KB Output is correct
4 Correct 10 ms 23896 KB Output is correct
5 Correct 18 ms 27224 KB Output is correct
6 Correct 82 ms 33120 KB Output is correct
7 Correct 10 ms 23896 KB Output is correct
8 Correct 74 ms 33100 KB Output is correct
9 Correct 82 ms 35092 KB Output is correct
10 Correct 115 ms 39220 KB Output is correct
11 Correct 10 ms 23896 KB Output is correct
12 Correct 9 ms 23944 KB Output is correct
13 Correct 9 ms 23896 KB Output is correct
14 Correct 113 ms 37620 KB Output is correct
15 Correct 69 ms 31804 KB Output is correct
16 Correct 101 ms 35140 KB Output is correct
17 Correct 10 ms 23944 KB Output is correct
18 Correct 10 ms 23900 KB Output is correct
19 Correct 10 ms 23900 KB Output is correct
20 Correct 112 ms 37172 KB Output is correct
21 Correct 10 ms 23900 KB Output is correct
22 Correct 10 ms 23900 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 9 ms 23900 KB Output is correct
4 Correct 10 ms 23704 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23948 KB Output is correct
7 Correct 11 ms 23860 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct

Subtask #5
14.7580402392 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 11 ms 23900 KB Output is partially correct
2 Correct 96 ms 70984 KB Output is correct
3 Partially correct 121 ms 78284 KB Output is partially correct
4 Partially correct 180 ms 99616 KB Output is partially correct

Subtask #6
45.9139029664 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 11 ms 23900 KB Output is partially correct
2 Correct 96 ms 70984 KB Output is correct
3 Partially correct 121 ms 78284 KB Output is partially correct
4 Partially correct 180 ms 99616 KB Output is partially correct
5 Partially correct 237 ms 101404 KB Output is partially correct
6 Partially correct 214 ms 100636 KB Output is partially correct
7 Partially correct 224 ms 100888 KB Output is partially correct
8 Partially correct 209 ms 100388 KB Output is partially correct
9 Partially correct 123 ms 79732 KB Output is partially correct
10 Partially correct 183 ms 100132 KB Output is partially correct
11 Partially correct 205 ms 99892 KB Output is partially correct
12 Partially correct 123 ms 78496 KB Output is partially correct
13 Correct 129 ms 71752 KB Output is correct
14 Partially correct 143 ms 79424 KB Output is partially correct
15 Partially correct 145 ms 79592 KB Output is partially correct
16 Partially correct 12 ms 25436 KB Output is partially correct
17 Correct 107 ms 71152 KB Output is correct
18 Correct 109 ms 71244 KB Output is correct
19 Partially correct 128 ms 78524 KB Output is partially correct
20 Partially correct 223 ms 100164 KB Output is partially correct
21 Partially correct 180 ms 99804 KB Output is partially correct
22 Partially correct 184 ms 99876 KB Output is partially correct