oj.uz

답안 #1071763

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1071763 2024-08-23T11:00:06 Z Faisal_Saqib 자동 인형 (IOI18_doll) C++17
20.758 / 100
 76 ms 14584 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)
{
	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;
}
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;
			vll order=fast_order(pw);
			vll fl(pw,1);
			// cout<<"before\n";
			for(int j=zxp;j<pw;j++)
				fl[j-zxp]=-NM;
			for(int j=0;j<pw;)
			{
				order[j]--;
				while(fl[order[j]]==-NM)
					j++;
				fl[order[j]]=child[i][cpp];
				j++;
				cpp++;
			}
			// cout<<"After\n";
			// for(int j=0;j<pw;j++)
			// {
			// 	cout<<fl[j]<<' ';
			// }
			// cout<<endl;
			ll og=label;
			father_of_all=-label-1;
			childx.clear();
			childy.clear();
			order_.clear();
			npp.clear();
			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;
		}
	}
	answer(ans,XP,YP);
}

Compilation message

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

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 21 ms 7180 KB Output is correct
3 Correct 16 ms 5840 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 8 ms 3936 KB Output is correct
6 Correct 25 ms 8916 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 21 ms 7180 KB Output is correct
3 Correct 16 ms 5840 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 8 ms 3936 KB Output is correct
6 Correct 25 ms 8916 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 34 ms 8864 KB Output is correct
9 Correct 37 ms 10192 KB Output is correct
10 Correct 53 ms 13600 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 21 ms 7180 KB Output is correct
3 Correct 16 ms 5840 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 8 ms 3936 KB Output is correct
6 Correct 25 ms 8916 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 34 ms 8864 KB Output is correct
9 Correct 37 ms 10192 KB Output is correct
10 Correct 53 ms 13600 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Incorrect 67 ms 13296 KB wrong motion
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 444 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #5
14.7580402392 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB Output is partially correct
2 Correct 29 ms 9916 KB Output is correct
3 Partially correct 33 ms 10072 KB Output is partially correct
4 Correct 47 ms 13400 KB Output is correct

Subtask #6
0.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB Output is partially correct
2 Correct 29 ms 9916 KB Output is correct
3 Partially correct 33 ms 10072 KB Output is partially correct
4 Correct 47 ms 13400 KB Output is correct
5 Incorrect 76 ms 14584 KB wrong motion
6 Halted 0 ms 0 KB -