제출 #117739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117739		sealnot123	고대 책들 (IOI17_books)	C++14	50 / 100	211 ms	19720 KiB

books

#include "books.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 1000007;
int n;
int mk[N];
vector<PII> inter,interx;
long long minimum_walk(vector<int> p, int s) {
    int a,b,c,d,i,j,k;
    int l,r;
    LL ans = 0;
    n = SZ(p);
    if(n==1) return 0;
    for(i=0;i<n;i++){
        if(p[i]==i || mk[i]) continue;
        l = r = i;
        mk[i] = 1;
        a = p[i];
        ans += abs(i-p[i]);
        while(a!=i){
            mk[a] = 1;
            ans += abs(a-p[a]);
            l = min(l, a);
            r = max(r, a);
            a = p[a];
        }
        inter.pb({l,r});
    }
    sort(inter.begin(),inter.end());
    l = r = -1;
    for(PII it : inter){
        if(it.x > r){
            if(l!=-1) interx.pb({l,r});
            l = it.x;
        }
        r = max(r, it.y);
    }
    if(l!=-1) interx.pb({l,r});
    for(i=0;i<SZ(interx);i++){
        PII it1 = interx[i];
//        printf("%d %d\n",it1.x,it1.y);
        if(it1.x<=s && it1.y>=s){
            int tmp = 1<<30;
            for(j=s;j>=0;j--){
                if(mk[j]){
                    tmp = min(tmp,s-j); break;
                }
            }
            for(j=s;j<n;j++){
                if(mk[j]){
                    tmp = min(tmp,j-s); break;
                }
            }
            ans += 2*tmp;
        }
        if(i+1==SZ(interx)) continue;
        PII it2 = interx[i+1];
        ans += 2*(it2.x-it1.y);
    }
    if(!interx.empty()){
        if(s<interx[0].x) ans += 2*(interx[0].x-s);
        if(s>interx.back().y) ans += 2*(s-interx.back().y);
    }
    return ans;
}
/*
7 4
1 0 6 5 4 2 3
*/

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

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:21:11: warning: unused variable 'b' [-Wunused-variable]
     int a,b,c,d,i,j,k;
           ^
books.cpp:21:13: warning: unused variable 'c' [-Wunused-variable]
     int a,b,c,d,i,j,k;
             ^
books.cpp:21:15: warning: unused variable 'd' [-Wunused-variable]
     int a,b,c,d,i,j,k;
               ^
books.cpp:21:21: warning: unused variable 'k' [-Wunused-variable]
     int a,b,c,d,i,j,k;
                     ^

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