제출 #117956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117956		sealnot123	고대 책들 (IOI17_books)	C++14	100 / 100	235 ms	26616 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 L[N],R[N],G[N];
void extend(int &l, int &r, int &ll, int &rr){
    ll = min(ll, min(L[G[l]], L[G[r]]));
    rr = max(rr, max(R[G[l]], R[G[r]]));
    while(ll < l || r < rr){
        if(ll < l){
            l--;
            ll = min(ll, L[G[l]]);
            rr = max(rr, R[G[l]]);
        }else{
            r++;
            ll = min(ll, L[G[r]]);
            rr = max(rr, R[G[r]]);
        }
    }
}
LL step(int l, int r, int ll, int rr){
    LL ans = 0;
    int i,j,k,a,b,c;
    while(ll < l || r < rr){
        int stepl = 0, stepr = 0, ch = 0;
        int xll, xrr, x_l, y_l, x_r, y_r;
        x_l = xll = l;
        y_l = xrr = r;
        while(x_l > ll && xrr == r){
            stepl += 2;
            x_l--;
            extend(x_l, y_l, xll, xrr);
        }
        if(xrr == r) ch = 1;
        x_r = xll = l;
        y_r = xrr = r;
        while(y_r < rr && xll == l){
            stepr += 2;
            y_r++;
            extend(x_r, y_r, xll, xrr);
        }
        if(xll == l) ch = 1;
        if(ch){
            ans += stepl + stepr;
            break;
        }else{
            ans += min(stepl, stepr);
            l = min(l, min(x_l, x_r));
            r = max(r, max(y_l, y_r));
        }
    }
    return ans;
}
long long minimum_walk(vector<int> p, int s) {
    int a, b, c = 0, d, i, j, k;
    int l = s, r = s;
    LL ans = 0;
    n = SZ(p);
    for(i=0; i<n; i++){
        ans += abs(i - p[i]);
        if(!G[i]){
            c++;
            a = i;
            L[c] = R[c] = i;
            do{
                G[a] = c;
                L[c] = min(L[c], a);
                R[c] = max(R[c], a);
                a = p[a];
            }while(a != i);
            if(i != p[i]){
                l = min(l, L[c]);
                r = max(r, R[c]);
            }
        }
    }
    int ll=s, rr=s, lll=s, rrr=s;
    extend(ll, rr, lll, rrr);
//    printf("%lld %d %d : %d %d\n", ans, l, r, ll, rr);
    return ans + step(ll, rr, l, r);
}
/*
4 0
2 0 1 3

7 4
1 0 6 5 4 2 3

8 4
7 1 2 0 3 5 6 4

8 4
7 5 6 0 3 2 1 4

5 2
3 4 2 0 1
*/

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

books.cpp: In function 'LL step(int, int, int, int)':
books.cpp:36:9: warning: unused variable 'i' [-Wunused-variable]
     int i,j,k,a,b,c;
         ^
books.cpp:36:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j,k,a,b,c;
           ^
books.cpp:36:13: warning: unused variable 'k' [-Wunused-variable]
     int i,j,k,a,b,c;
             ^
books.cpp:36:15: warning: unused variable 'a' [-Wunused-variable]
     int i,j,k,a,b,c;
               ^
books.cpp:36:17: warning: unused variable 'b' [-Wunused-variable]
     int i,j,k,a,b,c;
                 ^
books.cpp:36:19: warning: unused variable 'c' [-Wunused-variable]
     int i,j,k,a,b,c;
                   ^
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:68:12: warning: unused variable 'b' [-Wunused-variable]
     int a, b, c = 0, d, i, j, k;
            ^
books.cpp:68:22: warning: unused variable 'd' [-Wunused-variable]
     int a, b, c = 0, d, i, j, k;
                      ^
books.cpp:68:28: warning: unused variable 'j' [-Wunused-variable]
     int a, b, c = 0, d, i, j, k;
                            ^
books.cpp:68:31: warning: unused variable 'k' [-Wunused-variable]
     int a, b, c = 0, d, i, j, k;
                               ^

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