oj.uz

Submission #1073341

# Submission time Handle Problem Language Result Execution time Memory
1073341 2024-08-24T12:47:46 Z Faisal_Saqib Mechanical Doll (IOI18_doll) C++17
85.553 / 100
 176 ms 103232 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];
	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
			{
				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:226:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |  for(int j=0;j<a.size();j++)
      |              ~^~~~~~~~~
doll.cpp:229:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |  for(int j=1;j<cur.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:232:7: warning: unused variable 'lps' [-Wunused-variable]
  232 |   int lps=0;
      |       ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26968 KB Output is correct
2 Correct 26 ms 33748 KB Output is correct
3 Correct 20 ms 32720 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 11 ms 30556 KB Output is correct
6 Correct 25 ms 35540 KB Output is correct
7 Correct 5 ms 26972 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26968 KB Output is correct
2 Correct 26 ms 33748 KB Output is correct
3 Correct 20 ms 32720 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 11 ms 30556 KB Output is correct
6 Correct 25 ms 35540 KB Output is correct
7 Correct 5 ms 26972 KB Output is correct
8 Correct 35 ms 35552 KB Output is correct
9 Correct 39 ms 36804 KB Output is correct
10 Correct 55 ms 40400 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 27072 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26968 KB Output is correct
2 Correct 26 ms 33748 KB Output is correct
3 Correct 20 ms 32720 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 11 ms 30556 KB Output is correct
6 Correct 25 ms 35540 KB Output is correct
7 Correct 5 ms 26972 KB Output is correct
8 Correct 35 ms 35552 KB Output is correct
9 Correct 39 ms 36804 KB Output is correct
10 Correct 55 ms 40400 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 27072 KB Output is correct
14 Correct 66 ms 39924 KB Output is correct
15 Correct 36 ms 34372 KB Output is correct
16 Correct 68 ms 37772 KB Output is correct
17 Correct 4 ms 26968 KB Output is correct
18 Correct 5 ms 26972 KB Output is correct
19 Correct 4 ms 26972 KB Output is correct
20 Correct 63 ms 39668 KB Output is correct
21 Correct 4 ms 27224 KB Output is correct
22 Correct 6 ms 26972 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Correct 5 ms 27060 KB Output is correct
4 Correct 4 ms 27124 KB Output is correct
5 Correct 4 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 26972 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 100 ms 75788 KB Output is correct
3 Correct 127 ms 81232 KB Output is correct
4 Correct 176 ms 103232 KB Output is correct

Subtask #6
41.5530038336 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26972 KB Output is correct
2 Correct 100 ms 75788 KB Output is correct
3 Correct 127 ms 81232 KB Output is correct
4 Correct 176 ms 103232 KB Output is correct
5 Partially correct 68 ms 40176 KB Output is partially correct
6 Partially correct 69 ms 39668 KB Output is partially correct
7 Partially correct 67 ms 39772 KB Output is partially correct
8 Partially correct 63 ms 38640 KB Output is partially correct
9 Partially correct 95 ms 58952 KB Output is partially correct
10 Partially correct 109 ms 63556 KB Output is partially correct
11 Partially correct 64 ms 37840 KB Output is partially correct
12 Partially correct 42 ms 34040 KB Output is partially correct
13 Partially correct 48 ms 35076 KB Output is partially correct
14 Partially correct 45 ms 35320 KB Output is partially correct
15 Partially correct 49 ms 35608 KB Output is partially correct
16 Partially correct 8 ms 27228 KB Output is partially correct
17 Partially correct 41 ms 33780 KB Output is partially correct
18 Partially correct 41 ms 34752 KB Output is partially correct
19 Partially correct 41 ms 33776 KB Output is partially correct
20 Partially correct 59 ms 37240 KB Output is partially correct
21 Partially correct 68 ms 37576 KB Output is partially correct
22 Partially correct 60 ms 36848 KB Output is partially correct