oj.uz

Submission #1072647

# Submission time Handle Problem Language Result Execution time Memory
1072647 2024-08-24T01:37:27 Z Faisal_Saqib Mechanical Doll (IOI18_doll) C++17
65.6728 / 100
 160 ms 103944 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})
		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]);
		int lps=0;
		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;
			}
		}
		// 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:248:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  248 |   for(int j=0;j<a.size();j++)
      |               ~^~~~~~~~~
doll.cpp:251:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |   for(int j=1;j<cur.size();j++)
      |               ~^~~~~~~~~~~
doll.cpp:264:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  264 |     while(child[i].size()>pw)
      |           ~~~~~~~~~~~~~~~^~~
doll.cpp:290:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  290 |     for(int k=0;k<child[i].size();k++)
      |                 ~^~~~~~~~~~~~~~~~
doll.cpp:296:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  296 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
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 i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:253:7: warning: unused variable 'lps' [-Wunused-variable]
  253 |   int lps=0;
      |       ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 43 ms 34188 KB Output is correct
3 Correct 41 ms 32796 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 14 ms 30440 KB Output is correct
6 Correct 61 ms 36108 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 5 ms 26972 KB Output is correct
2 Correct 43 ms 34188 KB Output is correct
3 Correct 41 ms 32796 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 14 ms 30440 KB Output is correct
6 Correct 61 ms 36108 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 72 ms 36236 KB Output is correct
9 Correct 79 ms 38476 KB Output is correct
10 Correct 111 ms 42356 KB Output is correct
11 Correct 5 ms 26972 KB Output is correct
12 Correct 4 ms 26972 KB Output is correct
13 Correct 5 ms 27124 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 43 ms 34188 KB Output is correct
3 Correct 41 ms 32796 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 14 ms 30440 KB Output is correct
6 Correct 61 ms 36108 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 72 ms 36236 KB Output is correct
9 Correct 79 ms 38476 KB Output is correct
10 Correct 111 ms 42356 KB Output is correct
11 Correct 5 ms 26972 KB Output is correct
12 Correct 4 ms 26972 KB Output is correct
13 Correct 5 ms 27124 KB Output is correct
14 Correct 113 ms 40772 KB Output is correct
15 Correct 66 ms 35140 KB Output is correct
16 Correct 99 ms 38376 KB Output is correct
17 Correct 6 ms 26972 KB Output is correct
18 Correct 5 ms 27040 KB Output is correct
19 Correct 5 ms 27100 KB Output is correct
20 Correct 118 ms 40532 KB Output is correct
21 Correct 4 ms 26968 KB Output is correct
22 Correct 4 ms 27224 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 26972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
14.7580402392 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 26968 KB Output is partially correct
2 Correct 102 ms 75808 KB Output is correct
3 Partially correct 116 ms 83532 KB Output is partially correct
4 Correct 160 ms 103944 KB Output is correct

Subtask #6
34.914797876 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 26968 KB Output is partially correct
2 Correct 102 ms 75808 KB Output is correct
3 Partially correct 116 ms 83532 KB Output is partially correct
4 Correct 160 ms 103944 KB Output is correct
5 Partially correct 126 ms 42720 KB Output is partially correct
6 Partially correct 119 ms 42048 KB Output is partially correct
7 Partially correct 118 ms 42160 KB Output is partially correct
8 Partially correct 107 ms 40696 KB Output is partially correct
9 Partially correct 113 ms 59724 KB Output is partially correct
10 Partially correct 129 ms 65172 KB Output is partially correct
11 Partially correct 73 ms 38504 KB Output is partially correct
12 Partially correct 50 ms 34776 KB Output is partially correct
13 Partially correct 78 ms 36004 KB Output is partially correct
14 Partially correct 75 ms 37228 KB Output is partially correct
15 Partially correct 82 ms 36308 KB Output is partially correct
16 Partially correct 6 ms 27228 KB Output is partially correct
17 Partially correct 50 ms 33804 KB Output is partially correct
18 Partially correct 46 ms 34260 KB Output is partially correct
19 Partially correct 55 ms 33948 KB Output is partially correct
20 Partially correct 87 ms 37880 KB Output is partially correct
21 Partially correct 72 ms 37440 KB Output is partially correct
22 Partially correct 77 ms 37524 KB Output is partially correct