Submission #138672

#	Time	Username	Problem	Language	Result	Execution time	Memory
138672		almogwald	Ancient Books (IOI17_books)	C++14	12 / 100	2056 ms	504 KiB

books

#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>
#include "books.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define maxl 10000000000
typedef long long lol;
using namespace std;
typedef vector<int> veci;
typedef pair<int,int> point;
lol sum=0;
veci merge(veci a ,veci b){
	int i=0,j=0;
	veci ans;
	while(i<a.size()&&j<b.size()){
		if(a[i]<b[j]){
			ans.push_back(a[i++]);
			sum+=j;
		}else{
			ans.push_back(b[j++]);
		}
	}
	while(i<a.size()){
		ans.push_back(a[i++]);
		sum+=j;
	}
	while(j<b.size()){
		ans.push_back(b[j++]);
	}
	return ans;
}
veci mergesort(veci a){
	if(a.size()==1){
		return a;
	}
	veci b,c;
	fori(i,a.size()){
		if(i<a.size()/2){
			b.push_back(a[i]);
		}else{
			c.push_back(a[i]);
		}
	}
	b=mergesort(b);
	c=mergesort(c);
	return merge(b,c);
}
long long minimum_walk(vector<int> p, int s) {
	int n=p.size();
	vector<int> a(n,-1);
	int cur=s;
	do{
		sum+=abs(p[cur]-cur);
		cur= p[cur];
		a[cur]=0;
	}while(cur !=s);
	int num=1;
	vector<int> b(n+1,s);
	int mon=0;
	fori(i,n){

		if(p[i]==i||a[i]!=-1){
			continue;
		}
		int l=-10000000;
		int r=n;
		int cur=i;
		do{
			if(cur<s){
				l=max(l,cur);
			}else{
				r=min(r,cur);
			}
			sum+=abs(p[cur]-cur);
			cur= p[cur];
			a[cur]=num;
		}while(cur !=i);
		num++;
		b[r-1]=l;

	}
	if(sum==0){
		return sum;
	}
	int l=0;int r=n-1;
	while(p[l]==l){
		l++;
	}
	while(p[r]==r){
		r--;
	}
	vector<vector<point>> cons(n);
	fori(i,n-1){
		cons[i].push_back({i+1,1});
		cons[i+1].push_back({i,1});
	}
	fori(i,n){
		if(p[i]!=i){
			cons[i].push_back({p[i],0});
		}
	}
	veci dists(n,-1);
	veci bef(n,-1);
	int ll=s;
	int rr=s;
	set<pair<int,point>> ss;
	ss.insert({0,{s,s}});
	while(!ss.empty()){
		auto it=ss.begin();
		int cur=it->second.first;
		int rrr=it->second.second;
		int d=it->first;
		ss.erase(it);
		if(dists[cur]!=-1){
			continue;
		}
		bef[cur]=rrr;
		dists[cur]=d;
		while(cur>rr){
			rr++;
			ss.insert({d,{rr,cur}});
		}
		while(cur<ll){
			ll--;
			ss.insert({d,{ll,cur}});
		}
		fori(i,cons[cur].size()){
			ss.insert({d+cons[cur][i].second,{cons[cur][i].first,r}});
		}
	}
	//cout << a[l] <<' ' << a[r] << endl;
	while(a[l]!=a[r]){
		//cout << a[l] <<' ' << a[r] << endl;
		if(dists[l]>dists[r] || r==s){
			mon+=dists[l]-dists[bef[l]];
			l=bef[l];
		}else{
			mon+=dists[r]-dists[bef[r]];
			r=bef[r];
		}
	}
	mon+=dists[l];
	/*veci distr(n,-1);
	ll=r;
	rr=r;
	ss.insert({0,r});
	while(!ss.empty()){
		auto it=ss.begin();
		int cur=it->second;
		int d=it->first;
		ss.erase(it);
		if(distr[cur]!=-1){
			continue;
		}
		distr[cur]=d;

		fori(i,cons[cur].size()){
			ss.insert({d+cons[cur][i].second,cons[cur][i].first});
		}
	}
	veci distl(n,-1);
	ll=l;
	rr=l;
	ss.insert({0,l});
	while(!ss.empty()){
		auto it=ss.begin();
		int cur=it->second;
		int d=it->first;
		ss.erase(it);
		if(distl[cur]!=-1){
			continue;
		}
		distl[cur]=d;

		fori(i,cons[cur].size()){
			ss.insert({d+cons[cur][i].second,cons[cur][i].first});
		}
	}*/

	return sum+2*mon;
}

Compilation message (stderr)

books.cpp: In function 'veci merge(veci, veci)':
books.cpp:19:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
        ~^~~~~~~~~
books.cpp:19:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
                    ~^~~~~~~~~
books.cpp:27:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()){
        ~^~~~~~~~~
books.cpp:31:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j<b.size()){
        ~^~~~~~~~~
books.cpp: In function 'veci mergesort(veci)':
books.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
books.cpp:41:7:
  fori(i,a.size()){
       ~~~~~~~~~~                
books.cpp:41:2: note: in expansion of macro 'fori'
  fori(i,a.size()){
  ^~~~
books.cpp:42:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<a.size()/2){
      ~^~~~~~~~~~~
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
books.cpp:131:8:
   fori(i,cons[cur].size()){
        ~~~~~~~~~~~~~~~~~~       
books.cpp:131:3: note: in expansion of macro 'fori'
   fori(i,cons[cur].size()){
   ^~~~

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