oj.uz

Submission #51056

# Submission time Handle Problem Language Result Execution time Memory
51056 2018-06-15T21:54:39 Z FLDutchman Ancient Books (IOI17_books) C++14
0 / 100
 42 ms 48024 KB 
#include "books.h"
#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define fst first
#define snd second
#define FOR(i, l, r) for(int i = l; i < r; i++)

typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int NMAX = 1e6 + 10;
const int INF = 1e9;

vi cycles[NMAX];
int numCycles, N;
bitset<NMAX> vis;
vi point;

void flood(int n, int c){
	//cout << "Flood " << n << " " << c << endl;
	cycles[c].pb(n);
	int k = point[n];
	vis[n] = 1;
	if(!vis[k]) flood(k, c); 
}

// 
ii bounds(int p, int c){
	//cout << p << endl;
	auto &cy = cycles[c];	
	if(cy[0] > p) return {-1, cy[0]};
	if(cy[cy.size()-1] <= p) return {cy[cy.size()-1], INF};
	auto x = lower_bound(cycles[c].begin(), cycles[c].end(), p);
	return {*x, *(++x)};
}

long long minimum_walk(std::vector<int> p, int s) {
	vis.reset();
	point = p;
	N = p.size();
	FOR(i, 0, N) if(!vis[i]) flood(i, numCycles++);
	FOR(i, 0, numCycles) sort(cycles[i].begin(), cycles[i].end());
	//cout << "Preprocessed" << endl;
	//ii k = bounds(2, 1);
	//cout << k.fst << " " << k.snd << endl;
	//Find segments:
	vii segs;
	int rm = 0;
	int lm = 0;
	//cout << "numCycles: " << numCycles << endl;
	FOR(i, 0, numCycles){
		//cout << lm << " " << rm << endl;
		if(rm <= cycles[i][0]) {
			if(rm - lm > 1) segs.pb({lm, rm});
			lm = cycles[i][0]; rm = cycles[i].back()+1;
		}
		rm = max(rm, cycles[i].back());
	}

	if(rm - lm > 1) segs.pb({lm, rm});

	//cout << segs.size() << endl;
	int dist = 0;
	if(segs.size() > 0)
		dist  = segs[0].fst*2;
	FOR(i, 0, N) dist += abs(i - p[i]);
	//cout << dist << endl;
	//cout << segs.size() << endl;
	FOR(i, 0, segs.size()-1){
		dist += 2*(segs[i+1].fst - segs[i].snd);
	}

	return dist;
}
/*
3 1
0 2 1

4 0
0 1 3 2

4 0
2 3 0 1
*/

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:8:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
books.cpp:73:6:
  FOR(i, 0, segs.size()-1){
      ~~~~~~~~~~~~~~~~~~~               
books.cpp:73:2: note: in expansion of macro 'FOR'
  FOR(i, 0, segs.size()-1){
  ^~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct
3 Correct 22 ms 23992 KB Output is correct
4 Correct 22 ms 24060 KB Output is correct
5 Correct 21 ms 24136 KB Output is correct
6 Correct 21 ms 24136 KB Output is correct
7 Correct 21 ms 24148 KB Output is correct
8 Correct 22 ms 24176 KB Output is correct
9 Runtime error 42 ms 48024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct
3 Correct 22 ms 23992 KB Output is correct
4 Correct 22 ms 24060 KB Output is correct
5 Correct 21 ms 24136 KB Output is correct
6 Correct 21 ms 24136 KB Output is correct
7 Correct 21 ms 24148 KB Output is correct
8 Correct 22 ms 24176 KB Output is correct
9 Runtime error 42 ms 48024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct
3 Correct 22 ms 23992 KB Output is correct
4 Correct 22 ms 24060 KB Output is correct
5 Correct 21 ms 24136 KB Output is correct
6 Correct 21 ms 24136 KB Output is correct
7 Correct 21 ms 24148 KB Output is correct
8 Correct 22 ms 24176 KB Output is correct
9 Runtime error 42 ms 48024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 48024 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct
3 Correct 22 ms 23992 KB Output is correct
4 Correct 22 ms 24060 KB Output is correct
5 Correct 21 ms 24136 KB Output is correct
6 Correct 21 ms 24136 KB Output is correct
7 Correct 21 ms 24148 KB Output is correct
8 Correct 22 ms 24176 KB Output is correct
9 Runtime error 42 ms 48024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -