oj.uz

Submission #1071677

# Submission time Handle Problem Language Result Execution time Memory
1071677 2024-08-23T09:54:31 Z Faisal_Saqib Mechanical Doll (IOI18_doll) C++17
16 / 100
 1000 ms 21684 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],final[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)
{
	// cout<<"Range "<<l<<' '<<r<<' '<<" p: ";
	// for(int i=l;i<=r;i++)
	// {
	// 	cout<<p[i]<<' ';
	// }
	// cout<<endl;
	if((l-r)==0){
		// cout<<"Assigned ";
		if(p[l]==-NM)
		{
			// cout<<father_of_all<<endl;
			return father_of_all;
		}
		// cout<<p[l]<<endl;
		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)
	{
		// all minus one is subtree
		// cout<<"Range "<<l<<' '<<r<<endl;
		// cout<<"Child: "<<father_of_all<<' '<<father_of_all<<endl;
		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);
		// cout<<"Range "<<l<<' '<<r<<endl;
		// cout<<"Child: "<<XP.back()<<' '<<YP.back()<<endl;
	}
	// cout<<"Assigned to range "<<l<<' '<<r<<' ';
	// cout<<usep<<endl;
	order_.pb(fk);
	npp.pb(usep);
	return usep;
}
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;
	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(),cpp=0;
			for(int j=zxp;j<pw;j++)
			{
				cp[cpp]=-NM;
				cpp++;
			}
			for(int j=0;j<child[i].size();j++)
			{
				cp[cpp]=child[i][j];
				cpp++;
			}
			vll order=fast_order(pw);
			vll fl(pw);
			for(int j=0;j<pw;j++)
			{
				order[j]--;
				fl[order[j]]=cp[j];
				final[order[j]]=cp[j];
			}
			// cout<<"final: ";
			// for(int j=0;j<pw;j++)
			// 	cout<<final[j]<<' ';
			// cout<<endl;
			// what switches?
			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();
			label_it(fl,0,pw-1);
			// cout<<"X: ";
			// for(auto i:childx)
			// {
			// 	cout<<i<<' ';
			// }
			// cout<<endl;
			// cout<<"Y: ";
			// for(auto i:childy)
			// {
			// 	cout<<i<<' ';
			// }
			// cout<<endl;
			// cout<<"Order: ";
			// for(auto i:order_)
			// 	cout<<i<<' ';
			// cout<<endl;
			// cout<<"npp: ";
			// for(auto i:npp)
			// 	cout<<i<<' ';
			// cout<<endl;
			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;
		}
		/*
		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]);
		}
		*/
	}
	// cout<<"ans\n";
	// for(int i=0;i<=m;i++)
	// {
	// 	cout<<ans[i]<<' ';
	// }
	// 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<<XP[i]<<' '<<YP[i]<<endl;
	// }
	answer(ans,XP,YP);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:95:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for(int j=0;j<a.size();j++)
      |              ~^~~~~~~~~
doll.cpp:98:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int j=1;j<cur.size();j++)
      |              ~^~~~~~~~~~~
doll.cpp:111:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |    while(child[i].size()>pw)
      |          ~~~~~~~~~~~~~~~^~~
doll.cpp:119:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    for(int j=0;j<child[i].size();j++)
      |                ~^~~~~~~~~~~~~~~~
doll.cpp:168:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |    for(int i=0;i<order_.size();i++)
      |                ~^~~~~~~~~~~~~~
doll.cpp:173:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |    for(int i=0;i<order_.size();i++)
      |                ~^~~~~~~~~~~~~~
doll.cpp:100:6: warning: unused variable 'lps' [-Wunused-variable]
  100 |  int lps=0;
      |      ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 18 ms 7124 KB Output is correct
3 Correct 15 ms 5804 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 3720 KB Output is correct
6 Correct 21 ms 8920 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 18 ms 7124 KB Output is correct
3 Correct 15 ms 5804 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 3720 KB Output is correct
6 Correct 21 ms 8920 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 41 ms 10832 KB Output is correct
9 Correct 36 ms 12228 KB Output is correct
10 Correct 53 ms 15644 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 0 ms 2392 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 18 ms 7124 KB Output is correct
3 Correct 15 ms 5804 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 3720 KB Output is correct
6 Correct 21 ms 8920 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 41 ms 10832 KB Output is correct
9 Correct 36 ms 12228 KB Output is correct
10 Correct 53 ms 15644 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 0 ms 2392 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 70 ms 15348 KB Output is correct
15 Correct 39 ms 9788 KB Output is correct
16 Correct 60 ms 13044 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2492 KB Output is correct
20 Correct 60 ms 14912 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 0 ms 2396 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2396 KB Output is partially correct
2 Execution timed out 1070 ms 21684 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2396 KB Output is partially correct
2 Execution timed out 1070 ms 21684 KB Time limit exceeded
3 Halted 0 ms 0 KB -