oj.uz

Submission #1073212

# Submission time Handle Problem Language Result Execution time Memory
1073212 2024-08-24T10:32:38 Z Faisal_Saqib Mechanical Doll (IOI18_doll) C++17
65.6728 / 100
 192 ms 102460 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;
	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;
		// cout<<"SZ: "<<child[v].size()<<endl;
		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++;
				// 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:237:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |  for(int j=0;j<a.size();j++)
      |              ~^~~~~~~~~
doll.cpp:240:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |  for(int j=1;j<cur.size();j++)
      |              ~^~~~~~~~~~~
doll.cpp:255:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  255 |     while(child[i].size()>pw)
      |           ~~~~~~~~~~~~~~~^~~
doll.cpp:311:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  311 |     for(int k=0;k<child[i].size();k++)
      |                 ~^~~~~~~~~~~~~~~~
doll.cpp:323:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  323 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:328:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  328 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:243:7: warning: unused variable 'lps' [-Wunused-variable]
  243 |   int lps=0;
      |       ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 26968 KB Output is correct
2 Correct 47 ms 34188 KB Output is correct
3 Correct 45 ms 32796 KB Output is correct
4 Correct 11 ms 26968 KB Output is correct
5 Correct 16 ms 30556 KB Output is correct
6 Correct 66 ms 36108 KB Output is correct
7 Correct 10 ms 26968 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 26968 KB Output is correct
2 Correct 47 ms 34188 KB Output is correct
3 Correct 45 ms 32796 KB Output is correct
4 Correct 11 ms 26968 KB Output is correct
5 Correct 16 ms 30556 KB Output is correct
6 Correct 66 ms 36108 KB Output is correct
7 Correct 10 ms 26968 KB Output is correct
8 Correct 77 ms 36376 KB Output is correct
9 Correct 82 ms 38476 KB Output is correct
10 Correct 133 ms 42328 KB Output is correct
11 Correct 10 ms 26972 KB Output is correct
12 Correct 11 ms 26984 KB Output is correct
13 Correct 11 ms 26972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 26968 KB Output is correct
2 Correct 47 ms 34188 KB Output is correct
3 Correct 45 ms 32796 KB Output is correct
4 Correct 11 ms 26968 KB Output is correct
5 Correct 16 ms 30556 KB Output is correct
6 Correct 66 ms 36108 KB Output is correct
7 Correct 10 ms 26968 KB Output is correct
8 Correct 77 ms 36376 KB Output is correct
9 Correct 82 ms 38476 KB Output is correct
10 Correct 133 ms 42328 KB Output is correct
11 Correct 10 ms 26972 KB Output is correct
12 Correct 11 ms 26984 KB Output is correct
13 Correct 11 ms 26972 KB Output is correct
14 Correct 122 ms 40772 KB Output is correct
15 Correct 68 ms 35144 KB Output is correct
16 Correct 116 ms 38468 KB Output is correct
17 Correct 11 ms 26972 KB Output is correct
18 Correct 13 ms 27124 KB Output is correct
19 Correct 11 ms 26968 KB Output is correct
20 Correct 119 ms 40376 KB Output is correct
21 Correct 11 ms 27224 KB Output is correct
22 Correct 11 ms 26972 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 26968 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 11 ms 26972 KB Output is partially correct
2 Correct 117 ms 74048 KB Output is correct
3 Partially correct 117 ms 81756 KB Output is partially correct
4 Correct 192 ms 102460 KB Output is correct

Subtask #6
34.914797876 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 26972 KB Output is partially correct
2 Correct 117 ms 74048 KB Output is correct
3 Partially correct 117 ms 81756 KB Output is partially correct
4 Correct 192 ms 102460 KB Output is correct
5 Partially correct 125 ms 42584 KB Output is partially correct
6 Partially correct 131 ms 42040 KB Output is partially correct
7 Partially correct 119 ms 42164 KB Output is partially correct
8 Partially correct 104 ms 40696 KB Output is partially correct
9 Partially correct 109 ms 57920 KB Output is partially correct
10 Partially correct 126 ms 63064 KB Output is partially correct
11 Partially correct 76 ms 38468 KB Output is partially correct
12 Partially correct 52 ms 34724 KB Output is partially correct
13 Partially correct 76 ms 36004 KB Output is partially correct
14 Partially correct 75 ms 37228 KB Output is partially correct
15 Partially correct 81 ms 36316 KB Output is partially correct
16 Partially correct 12 ms 27224 KB Output is partially correct
17 Partially correct 52 ms 33804 KB Output is partially correct
18 Partially correct 52 ms 34260 KB Output is partially correct
19 Partially correct 55 ms 33944 KB Output is partially correct
20 Partially correct 88 ms 37880 KB Output is partially correct
21 Partially correct 92 ms 37588 KB Output is partially correct
22 Partially correct 82 ms 37524 KB Output is partially correct