oj.uz

Submission #1095804

# Submission time Handle Problem Language Result Execution time Memory
1095804 2024-10-03T08:00:53 Z owoovo Mechanical Doll (IOI18_doll) C++17
70.6719 / 100
 301 ms 32912 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=0;i<n;i++){
		use.push_back(trans[i]);
	}
	use.push_back(len-1);
	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:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i=0;i<use.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:71: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]
   71 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:74: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]
   74 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:85: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]
   85 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
14.7580402392 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Correct 158 ms 21472 KB Output is correct
3 Partially correct 155 ms 21440 KB Output is partially correct
4 Partially correct 281 ms 31648 KB Output is partially correct

Subtask #6
45.9139029664 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Correct 158 ms 21472 KB Output is correct
3 Partially correct 155 ms 21440 KB Output is partially correct
4 Partially correct 281 ms 31648 KB Output is partially correct
5 Partially correct 270 ms 32912 KB Output is partially correct
6 Partially correct 279 ms 32780 KB Output is partially correct
7 Partially correct 301 ms 32800 KB Output is partially correct
8 Partially correct 278 ms 32668 KB Output is partially correct
9 Partially correct 166 ms 21440 KB Output is partially correct
10 Partially correct 278 ms 32416 KB Output is partially correct
11 Partially correct 291 ms 32124 KB Output is partially correct
12 Partially correct 155 ms 21688 KB Output is partially correct
13 Correct 156 ms 22288 KB Output is correct
14 Partially correct 150 ms 22200 KB Output is partially correct
15 Partially correct 151 ms 22452 KB Output is partially correct
16 Partially correct 3 ms 1112 KB Output is partially correct
17 Correct 135 ms 20816 KB Output is correct
18 Correct 152 ms 21684 KB Output is correct
19 Partially correct 155 ms 21688 KB Output is partially correct
20 Partially correct 275 ms 32156 KB Output is partially correct
21 Partially correct 255 ms 32152 KB Output is partially correct
22 Partially correct 256 ms 32164 KB Output is partially correct