Submission #112345

#	Time	Username	Problem	Language	Result	Execution time	Memory
112345		updown1	Ancient Books (IOI17_books)	C++17	50 / 100	345 ms	86420 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
//#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN = 1000000;
//Global Variables
ll N, out = 0, loc[MAXN], comp[MAXN], at = 0;
///             element ,   element
pair<int, int> rng[MAXN];
///                comp
vector<pair<int, int> > rng2;
bool vis[MAXN];
///   element ,     comp
vector<int> elements[MAXN];

void go1(int at, int co) {
	if (comp[at] != -1) return;
	rng[co].a = min(rng[co].a, at);
	rng[co].b = max(rng[co].b, at);
	comp[at] = -2;
	elements[co].pb(at);
	out += abs(loc[at]-at);
	go1(loc[at], co);
}
void go(int at) {
	if (vis[at]) return;
	vis[at] = true;
	go(loc[at]);
}
void chg(int a, int b) {
    for (int i: elements[a]) comp[i] = b;
}

ll minimum_walk(vector<int> p, int s) {
	N = p.size();
	ffi {rng[i] = mp(N, -1); comp[i] = -1; loc[i] = p[i];}
	ffi if (comp[i] == -1) {
		go1(i, at);
		at++;
	}
	//w<< "from components: " << out<<e;
	sort(rng, rng+at);
	For (i, 0, at) {
	    /// only one element - delete
	    if (rng[i].a == rng[i].b) continue;
	    /// vector is empty
	    if (rng2.empty()) {
            rng2.pb(rng[i]);
            chg(i, 0);
            continue;
	    }
        /// fully emcompassed - delete
        /// intersect - combine
        if (rng[i].a < rng2.back().b && rng2.back().b < rng[i].b) {
            chg(i, rng2.size()-1);
            rng2.back().b = rng[i].b;
        }
        /// don't intersect
        if (rng2.back().b < rng[i].a) {
            chg(i, rng2.size());
            rng2.pb(rng[i]);
        }
	}
	at = rng2.size();
	For (i, 0, at) {
	    rng[i] = rng2[i];
	    //w<< rng[i].a << " " << rng[i].b<<e;
	}
	bool lef, right, inter = false;
	For (i, 0, at) {
        if (rng[i].a > s) right = true;
        if (rng[i].b < s) lef = true;
        if (rng[i].a <= s && s <= rng[i].b) inter = true;
	}

	int a1, a2;
	if (inter) {
        int dist = N+1;
        ffi if (comp[i] != -2) {
            if (dist > abs(s-i)) {
                dist = min(dist, abs(s-i));
                a1 = rng[comp[i]].a;
                a2 = rng[comp[i]].b;
            }
        }
        //w<< "dist: " << dist<<e;
        if (dist == N+1) dist = 0;
        out += 2*dist;
    }

	if (right) {
        int far = s;
        if (inter) {
            far = a2;
        }

        For (i, 0, at) if (rng[i].a > s) {
            out += 2*(rng[i].a - far);
            far = rng[i].b;
        }
	}

	if (left) {
        int far = s;
        if (inter) {
            far = a1;
        }
        for (int i=at-1; i>=0; i--) if (rng[i].b < s) {
            out += 2*(far - rng[i].b);
            far = rng[i].a;
            //w<< out<<e;
        }
	}
	return out;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:82:7: warning: variable 'lef' set but not used [-Wunused-but-set-variable]
  bool lef, right, inter = false;
       ^~~
books.cpp:122:27: warning: 'far' may be used uninitialized in this function [-Wmaybe-uninitialized]
             out += 2*(far - rng[i].b);
                      ~~~~~^~~~~~~~~~~
books.cpp:111:32: warning: 'far' may be used uninitialized in this function [-Wmaybe-uninitialized]
             out += 2*(rng[i].a - far);
                      ~~~~~~~~~~^~~~~~

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