oj.uz

Submission #1073344

# Submission time Handle Problem Language Result Execution time Memory
1073344 2024-08-24T12:50:09 Z Faisal_Saqib Mechanical Doll (IOI18_doll) C++17
100 / 100
 207 ms 105416 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;
		}
	}
	if(!use)
		return father_of_all;
	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;
		}
	}
	if(!use)
		return 0;
	int fk=fake_id;
	fake_id++;
	child_[fk].clear();
	state[fk]=0;
	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<<"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];
	{
		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
			{
				int zxp=child[i].size();
				ll pw=1;
				while(pw<zxp)
					pw*=2;
				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<<"For "<<i<<endl;
				// cout<<"Before\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<<"After\n";
				// for(int i=0;i<pw;i++)
				// {
				// 	cout<<fl[i]<<' ';
				// }
				// cout<<endl;
				// cout<<"Size "<<order_.size()<<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:116:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  116 |  if(my_order.size()==req_sz)return;
      |     ~~~~~~~~~~~~~~~^~~~~~~~
doll.cpp: In function 'void subtask(int, std::vector<int>)':
doll.cpp:145:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |  for(int j=0;j<a.size();j++)
      |              ~^~~~~~~~~
doll.cpp:148:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |  for(int j=1;j<cur.size();j++)
      |              ~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:227:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |   for(int j=1;j<a.size();j++)
      |               ~^~~~~~~~~
doll.cpp:301:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  301 |     for(int k=0;k<child[i].size();k++)
      |                 ~^~~~~~~~~~~~~~~~
doll.cpp:314:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  314 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:319:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  319 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:230:7: warning: unused variable 'lps' [-Wunused-variable]
  230 |   int lps=0;
      |       ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26972 KB Output is correct
2 Correct 57 ms 53788 KB Output is correct
3 Correct 61 ms 56436 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 11 ms 30556 KB Output is correct
6 Correct 90 ms 68236 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26972 KB Output is correct
2 Correct 57 ms 53788 KB Output is correct
3 Correct 61 ms 56436 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 11 ms 30556 KB Output is correct
6 Correct 90 ms 68236 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 102 ms 76484 KB Output is correct
9 Correct 133 ms 83404 KB Output is correct
10 Correct 207 ms 105416 KB Output is correct
11 Correct 4 ms 26968 KB Output is correct
12 Correct 4 ms 26972 KB Output is correct
13 Correct 5 ms 27120 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26972 KB Output is correct
2 Correct 57 ms 53788 KB Output is correct
3 Correct 61 ms 56436 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 11 ms 30556 KB Output is correct
6 Correct 90 ms 68236 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 102 ms 76484 KB Output is correct
9 Correct 133 ms 83404 KB Output is correct
10 Correct 207 ms 105416 KB Output is correct
11 Correct 4 ms 26968 KB Output is correct
12 Correct 4 ms 26972 KB Output is correct
13 Correct 5 ms 27120 KB Output is correct
14 Correct 196 ms 104352 KB Output is correct
15 Correct 123 ms 81192 KB Output is correct
16 Correct 182 ms 103644 KB Output is correct
17 Correct 5 ms 26972 KB Output is correct
18 Correct 4 ms 26972 KB Output is correct
19 Correct 4 ms 27072 KB Output is correct
20 Correct 164 ms 104704 KB Output is correct
21 Correct 4 ms 26968 KB Output is correct
22 Correct 4 ms 26972 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26972 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Correct 4 ms 27128 KB Output is correct
4 Correct 4 ms 26968 KB Output is correct
5 Correct 5 ms 26972 KB Output is correct
6 Correct 4 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 4 ms 27084 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26972 KB Output is correct
2 Correct 95 ms 74036 KB Output is correct
3 Correct 113 ms 80064 KB Output is correct
4 Correct 166 ms 101284 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26972 KB Output is correct
2 Correct 95 ms 74036 KB Output is correct
3 Correct 113 ms 80064 KB Output is correct
4 Correct 166 ms 101284 KB Output is correct
5 Correct 185 ms 103276 KB Output is correct
6 Correct 180 ms 102560 KB Output is correct
7 Correct 180 ms 102820 KB Output is correct
8 Correct 184 ms 102308 KB Output is correct
9 Correct 121 ms 80060 KB Output is correct
10 Correct 159 ms 102052 KB Output is correct
11 Correct 163 ms 101624 KB Output is correct
12 Correct 107 ms 80316 KB Output is correct
13 Correct 90 ms 74948 KB Output is correct
14 Correct 144 ms 81064 KB Output is correct
15 Correct 109 ms 81336 KB Output is correct
16 Correct 7 ms 28504 KB Output is correct
17 Correct 106 ms 74396 KB Output is correct
18 Correct 91 ms 74256 KB Output is correct
19 Correct 105 ms 80568 KB Output is correct
20 Correct 175 ms 102036 KB Output is correct
21 Correct 186 ms 101796 KB Output is correct
22 Correct 156 ms 101776 KB Output is correct