제출 #41013

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41013		alenam0161	Ancient Books (IOI17_books)	C++14	100 / 100	334 ms	178924 KiB

books

#include "books.h"
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>
using namespace std;
const int N = 3e6 + 7;
int group[N];
int mx[N];
bool used[N];
int par[N],lpar[N],rpar[N];
int fpar(int v) {
	return v == par[v] ? v : par[v] = fpar(par[v]);
}
void merge(int v, int u) {
	v = fpar(v);
	u = fpar(u);
	if (rand() & 1) {
		swap(u, v);
	}
	lpar[v] = min(lpar[v], lpar[u]);
	rpar[v] = max(rpar[v], rpar[u]);
	par[u] = v;
}
long long minimum_walk(std::vector<int> p, int s) {
	long long ans = 0;
	for (int i = 0; i < p.size(); ++i)
		par[i] = lpar[i] = rpar[i] = i;
	for (int i = 0; i < p.size(); ++i) {
		ans += abs(i - p[i]);
		merge(i, p[i]);
	}
	stack<int> st;
	for (int i = 0; i < p.size(); ++i) {
		int P = fpar(i);

		if (i == lpar[P]) {
			st.push(i);
		}
		else {
			while (fpar(i) != fpar(st.top())) {
				merge(i, st.top());
				st.pop();
			}
		}
		if (i == rpar[fpar(i)])st.pop();
	}
	int L = 0, R = p.size() - 1;
	for (int i = p.size() - 1; i > 0; i--) { if (p[i] != i)break; R--; }
	for (int i = 0; i < p.size(); ++i) { if (p[i] != i)break;  L++; }
	int Main = fpar(s);
	int cl = lpar[Main];
	int cr = rpar[Main];
	while (cl > L || cr < R) {
		int howl = 0, ul = cl;
		while (ul > L) {
			ul--;
			howl++;
			int cur = fpar(ul);
			ul = lpar[cur];
			if (rpar[cur] > cr)break;
		}
		int howr = 0, ur = cr;
		while (ur < R) {
			ur++; howr++;
			int cur = fpar(ur);
			ur = rpar[cur];
			if (lpar[cur] < cl)break;
		}
		if (fpar(ul) == fpar(ur)) {
			int x = fpar(ul);
			cl = lpar[x];
			cr = rpar[x];
			ans += min(howl, howr) * 2;
		}
		else {
			cl = ul; cr = ur;
			ans += howl * 2 + howr * 2;
		}
	}

	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); ++i)
                    ^
books.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); ++i) {
                    ^
books.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); ++i) {
                    ^
books.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); ++i) { if (p[i] != i)break;  L++; }
                    ^

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