oj.uz

Submission #1072251

# Submission time Handle Problem Language Result Execution time Memory
1072251 2024-08-23T16:01:31 Z Faisal_Saqib Mechanical Doll (IOI18_doll) C++17
70.6719 / 100
 203 ms 100860 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]]);
}
void create_circuit(int m, std::vector<int> a)
{
	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);
				for(int j=0;j<zxp;j++)
					fl[j]=child[i][j];
				for(int j=zxp;j<pw;j++)
					fl[j]=-NM;
				if(fl[zxp-1]==0)
					swap(fl[zxp-1],fl[pw-1]);
				// 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 create_circuit(int, std::vector<int>)':
doll.cpp:150:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |   for(int j=1;j<a.size();j++)
      |               ~^~~~~~~~~
doll.cpp:167:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  167 |     while(child[i].size()>pw)
      |           ~~~~~~~~~~~~~~~^~~
doll.cpp:224:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |     for(int k=0;k<child[i].size();k++)
      |                 ~^~~~~~~~~~~~~~~~
doll.cpp:236:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:241:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  241 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:153:7: warning: unused variable 'lps' [-Wunused-variable]
  153 |   int lps=0;
      |       ^~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 12 ms 23944 KB Output is correct
3 Correct 10 ms 23896 KB Output is correct
4 Correct 9 ms 23920 KB Output is correct
5 Correct 10 ms 23896 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 10 ms 23900 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct

Subtask #5
14.7580402392 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 23900 KB Output is partially correct
2 Correct 106 ms 70076 KB Output is correct
3 Partially correct 122 ms 78272 KB Output is partially correct
4 Partially correct 184 ms 98976 KB Output is partially correct

Subtask #6
45.9139029664 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 23900 KB Output is partially correct
2 Correct 106 ms 70076 KB Output is correct
3 Partially correct 122 ms 78272 KB Output is partially correct
4 Partially correct 184 ms 98976 KB Output is partially correct
5 Partially correct 172 ms 100860 KB Output is partially correct
6 Partially correct 187 ms 100244 KB Output is partially correct
7 Partially correct 187 ms 100444 KB Output is partially correct
8 Partially correct 190 ms 99936 KB Output is partially correct
9 Partially correct 123 ms 79560 KB Output is partially correct
10 Partially correct 187 ms 99748 KB Output is partially correct
11 Partially correct 203 ms 99284 KB Output is partially correct
12 Partially correct 128 ms 78556 KB Output is partially correct
13 Correct 116 ms 70844 KB Output is correct
14 Partially correct 133 ms 79252 KB Output is partially correct
15 Partially correct 128 ms 79544 KB Output is partially correct
16 Partially correct 12 ms 25312 KB Output is partially correct
17 Correct 111 ms 70252 KB Output is correct
18 Correct 101 ms 70340 KB Output is correct
19 Partially correct 125 ms 78524 KB Output is partially correct
20 Partially correct 190 ms 99492 KB Output is partially correct
21 Partially correct 184 ms 99248 KB Output is partially correct
22 Partially correct 184 ms 99484 KB Output is partially correct