제출 #41009

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41009		alenam0161	고대 책들 (IOI17_books)	C++14	22 / 100	426 ms	20336 KiB

books

#include "books.h"
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>
using namespace std;
const int N = 1e6 + 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) {
		int a1 = fpar(i);
		int a2 = fpar(p[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(P);
		}
		else {
			merge(P, st.top());
		}
		if (i == rpar[P])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:30:7: warning: unused variable 'a1' [-Wunused-variable]
   int a1 = fpar(i);
       ^
books.cpp:31:7: warning: unused variable 'a2' [-Wunused-variable]
   int a2 = fpar(p[i]);
       ^
books.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); ++i) {
                    ^
books.cpp:49: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: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30