제출 #283832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
283832		hank55663	고대 책들 (IOI17_books)	C++14	42 / 100	768 ms	432476 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define x first
#define y second
int f[1000005];
int l[1000005];
int r[1000005];
int Find(int x){
	if(f[x]==x)return x;
	return f[x]=Find(f[x]);
}
int pre[1000005];
vector<pii> edge[2500005];
int dis[2500005];
int ok[1000005];
int vis[2500005];
int mindex;
struct node{
	node *l,*r;
	//list<int> v;
	int num;
	int a,b;
	node(int _a,int _b):a(_a),b(_b),l(NULL),r(NULL){
		num=mindex++;
	}
}*root;
void build(node *n){
	if(n->a==n->b){
		edge[n->num].pb(mp(n->a,0));
		return;
	}
	int mid=(n->a+n->b)/2;
	n->l=new node(n->a,mid);
	n->r=new node(mid+1,n->b);
	edge[n->num].push_back(mp(n->l->num,0));
	edge[n->num].push_back(mp(n->r->num,0));
	build(n->l);
	build(n->r);
}
void go(node *n,int l,int r,int x){
	if(n->a>=l&&n->b<=r){
		edge[x].push_back(mp(n->num,0));
		return ;
	}
	if(n->b<l||n->a>r)return;
	go(n->l,l,r,x);
	go(n->r,l,r,x);
}
long long minimum_walk(std::vector<int> p, int s) {
//	vector<pii> v;
	mindex=p.size();
	long long ans=0;
	int Min=1e9;
	int over=0;
	for(int i = 0;i<p.size();i++){
		if(p[i]!=i){
//			v.pb(mp(p[i],i));
			ans+=abs(p[i]-i);
		//	Min=min(Min,abs(i-s));
			if((i<s&&p[i]>s)||(i>s&&p[i]<s))over=1;
		}
		l[i]=1e9;
		r[i]=0;
		f[i]=i;
	}
	for(int i = 0;i<p.size();i++){
		f[Find(p[i])]=Find(i);
	}
	for(int i = 0;i<p.size();i++){
		l[Find(i)]=min(l[Find(i)],i);
		r[Find(i)]=max(r[Find(i)],i);
	}
	vector<pii> v;
	root = new node(0,p.size()-1);
	build(root);
	for(int i = 0;i<p.size();i++){
		if(f[i]==i&&l[i]!=r[i]){
			v.pb(mp(l[i],r[i]));
		}
	}
	if(v.empty())return 0;
	sort(v.begin(),v.end());
	int Max=v[0].y;
	ok[v[0].x]=1;
	for(auto it:v){
		if(Max<it.x){
			ok[Max]=1;
			ok[it.x]=1;
		}
		ans+=max(0,(it.x-Max)*2);
		Max=max(Max,it.y);
	}
	ok[Max]=1;
	if(!over){
	//	printf("?\n");
		if(s>Max||s<v[0].x){
			
			Min=max(s-Max,v[0].x-s);
		}
		else{
			//printf("%d ?\n",ans);
			Min=0;
		}
	}
	else{
		for(int i = 0;i<p.size();i++){
			if(p[i]<i){
				go(root,p[i],i,i);
			}
			if(p[i]>i){
				go(root,i,p[i],i);
			}
			if(i!=0){
				edge[i].pb(mp(i-1,1));
			}
			if(i!=p.size()){
				edge[i].pb(mp(i+1,1));
			}
		}
		deque<int> q;
		q.pb(s);
		fill(dis,dis+mindex,1e9);
		dis[s]=0;
		fill(vis,vis+mindex,0);
		while(!q.empty()){
			int x=q.front();
			q.pop_front();
			if(vis[x])continue;
			vis[x]=1;
			for(auto it:edge[x]){
				if(it.y==0){
					if(dis[it.x]>dis[x]){
						dis[it.x]=dis[x];
						q.push_front(it.x);
					}
				}
				else{
					if(dis[it.x]>dis[x]+1){
						dis[it.x]=dis[x]+1;
						q.push_back(it.x);
					}
				}
			}
		}
		for(int i = 0;i<p.size();i++){
			if(ok[i]){
				Min=min(Min,dis[i]);
			}
		}
	}
//	printf("%d\n",Min);
	return ans+Min*2;
}
/*
8
7 3 4 1 2 5 6 0
*/

컴파일 시 표준 에러 (stderr) 메시지

books.cpp: In constructor 'node::node(int, int)':
books.cpp:26:8: warning: 'node::b' will be initialized after [-Wreorder]
   26 |  int a,b;
      |        ^
books.cpp:23:8: warning:   'node* node::l' [-Wreorder]
   23 |  node *l,*r;
      |        ^
books.cpp:27:2: warning:   when initialized here [-Wreorder]
   27 |  node(int _a,int _b):a(_a),b(_b),l(NULL),r(NULL){
      |  ^~~~
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0;i<p.size();i++){
      |                ~^~~~~~~~~
books.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0;i<p.size();i++){
      |                ~^~~~~~~~~
books.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i = 0;i<p.size();i++){
      |                ~^~~~~~~~~
books.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i = 0;i<p.size();i++){
      |                ~^~~~~~~~~
books.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(int i = 0;i<p.size();i++){
      |                 ~^~~~~~~~~
books.cpp:120:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |    if(i!=p.size()){
      |       ~^~~~~~~~~~
books.cpp:149:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |   for(int i = 0;i<p.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 0 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 30