Submission #138580

#	Time	Username	Problem	Language	Result	Execution time	Memory
138580		almogwald	Ancient Books (IOI17_books)	C++14	50 / 100	210 ms	16016 KiB

books

#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#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;

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=-1;
	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;
	}
	bool ok=false;
	int l=s+1;int r=s;
	while(l!=0 || r!=n-1){
		mon++;
		bool ok=(l==0);
		int ll=l;
		int rr=r;
		if(l!=0){
			l--;
			ll--;
			cur=p[l];
			if(cur<s){
				ll=min(ll,cur);
			}else{
				rr=max(rr,cur);
			}
		}else{
			r++;
			rr++;
			cur=p[r];
			if(cur<s){
				ll=min(ll,cur);
			}else{
				rr=max(rr,cur);
			}
		}

		while(ll!=l|| r!=rr){
			ok=true;
			sum+=mon*2;
			mon=0;
			while(r<rr){
				r++;
				cur=p[r];
				if(cur<s){
					ll=min(ll,cur);
				}else{
					rr=max(rr,cur);
				}
			}
			while(l>ll){
				l--;
				cur=p[l];
				if(cur<s){
					ll=min(ll,cur);
				}else{
					rr=max(rr,cur);
				}
			}
		}
		if(l==0 && !ok){
			mon=0;
		}
	}
	return sum;
}

Compilation message (stderr)

books.cpp: In function 'veci merge(veci, veci)':
books.cpp:17:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
        ~^~~~~~~~~
books.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
                    ~^~~~~~~~~
books.cpp:25:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()){
        ~^~~~~~~~~
books.cpp:29:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j<b.size()){
        ~^~~~~~~~~
books.cpp: In function 'veci mergesort(veci)':
books.cpp:6:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
books.cpp:39:7:
  fori(i,a.size()){
       ~~~~~~~~~~                
books.cpp:39:2: note: in expansion of macro 'fori'
  fori(i,a.size()){
  ^~~~
books.cpp:40: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:82:7: warning: unused variable 'ok' [-Wunused-variable]
  bool ok=false;
       ^~

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