oj.uz

Submission #1095846

# Submission time Handle Problem Language Result Execution time Memory
1095846 2024-10-03T10:20:24 Z owoovo Mechanical Doll (IOI18_doll) C++17
86 / 100
 317 ms 34896 KB 
#include "doll.h"
#include<bits/stdc++.h>
#define F first 
#define S second 
using namespace std;
int m,n,a[800010],trans[800010],temp[800010];
int len;
vector<pair<int,pair<int,int>>> ans;
bool need(int l,int r){
	//if(n<=l&&r<len-1)return 0;
	 return 1;
}
bool build(int l,int r,int id){
	if(l+1==r){
		int lc=a[trans[l]],rc=a[trans[r]];
		if(lc==-1&&rc==-1)return 0;
		ans.push_back({-id,{lc,rc}});
		return 1;
	}
	int m=(l+r)>>1;
	int lc=id*2,rc=id*2+1;
	if(build(l,m,id*2)){
	}else{
		lc=1;
	}
	if(build(m+1,r,id*2+1)){
	}else{
		rc=1;
	}
	if(lc==1&&rc==1)return 0;
	ans.push_back({-id,{-lc,-rc}});
	return 1;
}
void create_circuit(int M, std::vector<int> A) {
	vector<int> c,x,y;
	n=A.size();
	m=M;
	len=1;
	c.resize(m+1);
	for(int i=0;i<n;i++)a[i]=A[i];
	for(int i=0;i<=m;i++)c[i]=-1;
	while(len<n+1){
		for(int i=0;i<len;i++)temp[2*i]=trans[i];
		for(int i=0;i<len;i++)temp[2*i+1]=temp[2*i]+len;
		len*=2;
		for(int i=0;i<len;i++)trans[i]=temp[i];
	}
	vector<int> use;
	for(int i=len-n-1;i<len;i++){
		use.push_back(trans[i]);
	}
	sort(use.begin(),use.end());
	map<int,int> nmp;
	for(int i=0;i<use.size();i++){
		nmp.insert({use[i],i});
	}
	for(int i=0;i<len-1;i++){
		if(nmp.count(trans[i])!=0){
			trans[i]=nmp[trans[i]];
		}else{
			trans[i]=n+1;
		}
	}
	a[n]=0;
	a[n+1]=-1;
	build(0,len-1,1);
	sort(ans.begin(),ans.end());
	reverse(ans.begin(),ans.end());
	map<int,int> mp;
	for(int i=0;i<ans.size();i++){
		mp.insert({ans[i].F,i+1});
	}
	for(int i=0;i<ans.size();i++){
		//cout<<ans[i].F<<" "<<ans[i].S.F<<" "<<ans[i].S.S<<"\n";
		if(mp.count(ans[i].S.F)!=0){
			ans[i].S.F=-mp[ans[i].S.F];
		}
		if(mp.count(ans[i].S.S)!=0){
			ans[i].S.S=-mp[ans[i].S.S];
		}
	}
	x.resize(ans.size());
	y.resize(ans.size());
	for(int i=0;i<ans.size();i++){
		x[i]=ans[i].S.F;
		y[i]=ans[i].S.S;
	}
	answer(c,x,y);
	return;
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i=0;i<use.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 75 ms 12824 KB Output is correct
3 Correct 80 ms 12272 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 121 ms 18008 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 75 ms 12824 KB Output is correct
3 Correct 80 ms 12272 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 121 ms 18008 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 162 ms 23672 KB Output is correct
9 Correct 175 ms 24108 KB Output is correct
10 Correct 291 ms 34896 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Incorrect 0 ms 348 KB wrong motion
14 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 75 ms 12824 KB Output is correct
3 Correct 80 ms 12272 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 121 ms 18008 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 162 ms 23672 KB Output is correct
9 Correct 175 ms 24108 KB Output is correct
10 Correct 291 ms 34896 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Incorrect 0 ms 348 KB wrong motion
14 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 174 ms 22392 KB Output is correct
3 Correct 172 ms 22456 KB Output is correct
4 Correct 283 ms 33180 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 174 ms 22392 KB Output is correct
3 Correct 172 ms 22456 KB Output is correct
4 Correct 283 ms 33180 KB Output is correct
5 Correct 295 ms 34304 KB Output is correct
6 Correct 279 ms 34200 KB Output is correct
7 Correct 290 ms 34176 KB Output is correct
8 Correct 285 ms 33912 KB Output is correct
9 Correct 165 ms 22452 KB Output is correct
10 Correct 276 ms 33768 KB Output is correct
11 Correct 273 ms 33432 KB Output is correct
12 Correct 167 ms 22708 KB Output is correct
13 Correct 158 ms 23080 KB Output is correct
14 Correct 178 ms 23220 KB Output is correct
15 Correct 178 ms 23224 KB Output is correct
16 Correct 4 ms 996 KB Output is correct
17 Correct 147 ms 21768 KB Output is correct
18 Correct 161 ms 22712 KB Output is correct
19 Correct 188 ms 22712 KB Output is correct
20 Correct 317 ms 33632 KB Output is correct
21 Correct 286 ms 33456 KB Output is correct
22 Correct 297 ms 33528 KB Output is correct