oj.uz

Submission #1095799

# Submission time Handle Problem Language Result Execution time Memory
1095799 2024-10-03T07:51:06 Z owoovo Mechanical Doll (IOI18_doll) C++17
37 / 100
 170 ms 30988 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;
}
void build(int l,int r,int id){
	if(l+1==r){
		ans.push_back({-id,{a[trans[l]],a[trans[r]]}});
		return;
	}
	int m=(l+r)>>1;
	int lc=id*2,rc=id*2+1;
	if(need(l,m)){
		build(l,m,id*2);
	}else{
		lc=1;
	}
	if(need(m+1,r)){
		build(m+1,r,id*2+1);
	}else{
		rc=1;
	}
	ans.push_back({-id,{-lc,-rc}});
	return;
}
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];
	}
	for(int i=n;i<len-1;i++)a[i]=-1;
	a[len-1]=0;
	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:53: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]
   53 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:56: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]
   56 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:67: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]
   67 |  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
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 #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 153 ms 29184 KB Output is partially correct
3 Partially correct 161 ms 29072 KB Output is partially correct
4 Partially correct 170 ms 29744 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 153 ms 29184 KB Output is partially correct
3 Partially correct 161 ms 29072 KB Output is partially correct
4 Partially correct 170 ms 29744 KB Output is partially correct
5 Partially correct 162 ms 30988 KB Output is partially correct
6 Partially correct 170 ms 30892 KB Output is partially correct
7 Partially correct 156 ms 30876 KB Output is partially correct
8 Partially correct 151 ms 30636 KB Output is partially correct
9 Partially correct 161 ms 29116 KB Output is partially correct
10 Partially correct 167 ms 30380 KB Output is partially correct
11 Partially correct 160 ms 30124 KB Output is partially correct
12 Partially correct 144 ms 29380 KB Output is partially correct
13 Partially correct 148 ms 29632 KB Output is partially correct
14 Partially correct 150 ms 29860 KB Output is partially correct
15 Partially correct 152 ms 29972 KB Output is partially correct
16 Partially correct 4 ms 1112 KB Output is partially correct
17 Correct 70 ms 15556 KB Output is correct
18 Partially correct 151 ms 29192 KB Output is partially correct
19 Partially correct 143 ms 29376 KB Output is partially correct
20 Partially correct 153 ms 30272 KB Output is partially correct
21 Partially correct 154 ms 30132 KB Output is partially correct
22 Partially correct 165 ms 30128 KB Output is partially correct