oj.uz

답안 #52181

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52181 2018-06-24T14:17:41 Z 김세빈(#1331) 고대 책들 (IOI17_books) C++11
0 / 100
 22 ms 24292 KB 
#include "books.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

vector <int> V[1010101], X;
vector <pii> P;
int T[3030303];
int L[1010101], R[1010101];
int chk[1010101], K[1010101];
int n,cnt,sz;
ll ans;

int abs(int x)
{
	return x > 0? x : -x;
}

int find_min(int l,int r)
{
	l += sz, r += sz;
	int ret = 0;
	
	for(;l<r;){
		if((l & 1) && L[ret] > L[T[l]]) ret = T[l];
		if((~r & 1) && L[ret] > L[T[r]]) ret = T[r];
		l = ++l >> 1;
		r = --r >> 1;
	}
	if(l == r && L[ret] > L[T[l]]) ret = T[l];
	
	return ret;
}

void insert(int p,int v)
{
	p += sz;
	T[p] = v;
	
	for(p>>=1;p;p>>=1){
		if(L[T[p<<1]] < L[T[p<<1|1]]) T[p] = T[p<<1];
		else T[p] = T[p<<1|1];
	}
}
 
bool comp(int a,int b)
{
	return L[a] < L[b];
}

ll minimum_walk(vector <int> p, int s)
{
	int i,t,m,k,f;
	
	n = p.size();
	
	for(sz=1;sz<n;sz<<=1);
	
	for(i=0;i<n;i++) if(!chk[i] && i != p[i]){
		cnt ++;
		chk[i] = cnt;
		V[cnt].push_back(i);
		L[cnt] = R[cnt] = i;
		K[cnt] = cnt;
		
		ans += abs(i - p[i]);
		
		for(int j=p[i];j!=i;j=p[j]){
			chk[j] = cnt;
			V[cnt].push_back(j);
			R[cnt] = max(R[cnt], j);
			
			ans += abs(j - p[j]);
		}
	}
	
	L[0] = n+1;
	
	sort(K+1, K+cnt+1, comp);
	
	for(i=1;i<=cnt;i++){
		t = K[i];
		f = find_min(L[t], R[t]);
		
		if(f){
			for(int j: V[t]){
				V[f].push_back(j);
				R[f] = max(R[f], j);
				chk[j] = f;
				insert(j, f);
			}
			V[t].clear();
		}
		else{
			for(int j: V[t]){
				insert(j, t);
			}
		}
	}
	
	for(i=1;i<=cnt;i++){
		t = K[i];
		if(V[t].empty()) continue;
		f = find_min(L[t], R[t]);
		
		if(L[f] < L[t]){
			for(int j: V[t]){
				V[f].push_back(j);
				R[f] = max(R[f], j);
				chk[j] = f;
				insert(j, f);
			}
			V[t].clear();
		}
	}
	
	for(i=1;i<=cnt;i++){
		t = K[i];
		if(!V[t].empty()){
			P.push_back(pii(L[t], R[t]));
			if(L[t] <= s && s <= R[t]){
				sort(V[t].begin(), V[t].end());
				X.push_back(t);
			}
		}
	}
	
	sort(P.begin(), P.end());
	
	t = P[0].first;
	
	for(i=k=0;i<P.size();i++){
		if(P[i].second < t) continue;
		ans += 2 * (P[i].first - t);
		t = max(t, P[i].second);
	}
	
	if(!X.empty()){
		for(i=0;i<X.size()-1;i++){
			k += min(abs(*lower_bound(V[X[i]].begin(), V[X[i]].end(), L[X[i+1]]) - L[X[i+1]]), abs(*upper_bound(V[X[i]].begin(), V[X[i]].end(), R[X[i+1]]) - R[X[i+1]]));
		}
		k += min(abs(*lower_bound(V[X[i]].begin(), V[X[i]].end(), s) - s), abs(*upper_bound(V[X[i]].begin(), V[X[i]].end(), s) - s));
	}
	
	return ans + k * 2;
}

Compilation message

books.cpp: In function 'int find_min(int, int)':
books.cpp:31:5: warning: operation on 'l' may be undefined [-Wsequence-point]
   l = ++l >> 1;
   ~~^~~~~~~~~~
books.cpp:32:5: warning: operation on 'r' may be undefined [-Wsequence-point]
   r = --r >> 1;
   ~~^~~~~~~~~~
books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:136:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=k=0;i<P.size();i++){
            ~^~~~~~~~~
books.cpp:143:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<X.size()-1;i++){
           ~^~~~~~~~~~~
books.cpp:57:10: warning: unused variable 'm' [-Wunused-variable]
  int i,t,m,k,f;
          ^

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 24056 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 24056 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 24056 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 24292 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3884'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 24056 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -