Submission #780529

#	Time	Username	Problem	Language	Result	Execution time	Memory
780529		I_Love_EliskaM_	Ancient Books (IOI17_books)	C++14	50 / 100	105 ms	20312 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) {return a+rng()%(b-a+1);}
#define all(x) x.begin(),x.end()
using ll = long long;

int ok(vector<int>&a){forn(i,a.size())if(a[i]!=i)return 0;return 1;}

ll minimum_walk(vector<int>a, int st) {
	if (ok(a)) return 0;
	ll ans=0;
	int n=a.size(); if (st!=0) return 0;

	vector<pi> v;
	vector<int> vis(n,0);

	int L=0, R=n-1;
	while (a[R]==R) --R;

	forn(i,n) {
		if (i<L || R<i) continue;
		if (vis[i]) continue;
		ll f=0;
		int l=n, r=-1;
		int p=i;
		while (!vis[p]) {
			vis[p]=1;
			l=min(l,p); r=max(r,p);
			f+=abs(a[p]-p);
			p=a[p];
		}
		v.pb({l,r});
		ans+=f;
	}
	sort(all(v));
	if (v.size()) ans-=2;
	int r=-1;
	for(auto&x:v) {
		if (x.f>r) ans+=2;
		r=max(r,x.s);
	}
	return ans;

}

Compilation message (stderr)

books.cpp: In function 'int ok(std::vector<int>&)':
books.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
   14 | int ok(vector<int>&a){forn(i,a.size())if(a[i]!=i)return 0;return 1;}
      |                            ~~~~~~~~~~
books.cpp:14:23: note: in expansion of macro 'forn'
   14 | int ok(vector<int>&a){forn(i,a.size())if(a[i]!=i)return 0;return 1;}
      |                       ^~~~

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