oj.uz

답안 #1072264

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1072264 2024-08-23T16:07:07 Z Faisal_Saqib 자동 인형 (IOI18_doll) C++17
86.6719 / 100
 231 ms 100380 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);
				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++;
				// 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:312:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  312 |     for(int k=0;k<child[i].size();k++)
      |                 ~^~~~~~~~~~~~~~~~
doll.cpp:324:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  324 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:329:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  329 |     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 30600 KB Output is correct
3 Correct 50 ms 29120 KB Output is correct
4 Correct 10 ms 23896 KB Output is correct
5 Correct 21 ms 27228 KB Output is correct
6 Correct 71 ms 32272 KB Output is correct
7 Correct 11 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 30600 KB Output is correct
3 Correct 50 ms 29120 KB Output is correct
4 Correct 10 ms 23896 KB Output is correct
5 Correct 21 ms 27228 KB Output is correct
6 Correct 71 ms 32272 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 77 ms 32076 KB Output is correct
9 Correct 82 ms 34360 KB Output is correct
10 Correct 118 ms 37712 KB Output is correct
11 Correct 10 ms 23900 KB Output is correct
12 Correct 9 ms 23900 KB Output is correct
13 Correct 11 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 30600 KB Output is correct
3 Correct 50 ms 29120 KB Output is correct
4 Correct 10 ms 23896 KB Output is correct
5 Correct 21 ms 27228 KB Output is correct
6 Correct 71 ms 32272 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 77 ms 32076 KB Output is correct
9 Correct 82 ms 34360 KB Output is correct
10 Correct 118 ms 37712 KB Output is correct
11 Correct 10 ms 23900 KB Output is correct
12 Correct 9 ms 23900 KB Output is correct
13 Correct 11 ms 23896 KB Output is correct
14 Correct 121 ms 36164 KB Output is correct
15 Correct 76 ms 30848 KB Output is correct
16 Correct 107 ms 33860 KB Output is correct
17 Correct 14 ms 23900 KB Output is correct
18 Correct 11 ms 23900 KB Output is correct
19 Correct 11 ms 23900 KB Output is correct
20 Correct 120 ms 35652 KB Output is correct
21 Correct 10 ms 23896 KB Output is correct
22 Correct 11 ms 23896 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
14.7580402392 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 13 ms 23900 KB Output is partially correct
2 Correct 107 ms 69964 KB Output is correct
3 Partially correct 117 ms 78288 KB Output is partially correct
4 Correct 189 ms 98900 KB Output is correct

Subtask #6
45.9139029664 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 13 ms 23900 KB Output is partially correct
2 Correct 107 ms 69964 KB Output is correct
3 Partially correct 117 ms 78288 KB Output is partially correct
4 Correct 189 ms 98900 KB Output is correct
5 Correct 231 ms 100380 KB Output is correct
6 Correct 223 ms 99612 KB Output is correct
7 Correct 226 ms 99868 KB Output is correct
8 Correct 209 ms 99364 KB Output is correct
9 Partially correct 132 ms 78272 KB Output is partially correct
10 Correct 196 ms 99352 KB Output is correct
11 Partially correct 202 ms 98848 KB Output is partially correct
12 Partially correct 124 ms 78540 KB Output is partially correct
13 Correct 135 ms 71592 KB Output is correct
14 Partially correct 150 ms 79120 KB Output is partially correct
15 Partially correct 152 ms 79428 KB Output is partially correct
16 Partially correct 13 ms 25432 KB Output is partially correct
17 Correct 116 ms 70988 KB Output is correct
18 Correct 123 ms 70988 KB Output is correct
19 Partially correct 144 ms 78528 KB Output is partially correct
20 Correct 224 ms 99156 KB Output is correct
21 Correct 197 ms 98800 KB Output is correct
22 Correct 217 ms 99020 KB Output is correct