Submission #429140

#	Time	Username	Problem	Language	Result	Execution time	Memory
429140		Dremix10	Ancient Books (IOI17_books)	C++17	50 / 100	417 ms	28084 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define endl '\n'
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 1e6+5;
const ll INF = 2e18;
const int MOD = 1e9+7;

int l[N],r[N],par[N];

int find(int x){
    return (par[x] == x) ? x : par[x] = find(par[x]);
}

void join(int x, int y){
    x = find(x);
    y = find(y);
    if(x==y)return;
    par[y] = x;
    l[x] = min(l[x],l[y]);
    r[x] = max(r[x],r[y]);
}

long long minimum_walk(vector<int> p, int s) {
    int i,j,n = p.size();

    ll ans = 0;
    bool ok[n] = {};
    int cnt = 0;

    for(i=0;i<n;i++){
        if(p[i] == i){
            ok[i] = true;
            cnt++;
        }
        l[i] = i,r[i] = i,par[i] = i;
    }

    i = 0;

    while(cnt < n){
        while(ok[i]){
            i++;
            //ans++;
        }
        int fin = i;
        ans += abs(p[i] - i);
        i = p[i];
        ok[i] = true;
        cnt++;
        while(i != fin){
            join(i,fin);
            ans += abs(p[i] - i);
            i = p[i];
            ok[i] = true;
            cnt++;
        }
        //cout<<cnt<<" "<<ans<<" "<<i<<endl;
    }

    int low=s,high=s;
    i=s,j=s;
    while(i>0 || j<n-1){
        int curr;
        if(i >= 0)
            curr = find(i);
        else
            curr = find(j);
        bool ok = 0;

        low = min(low,l[curr]);
        while(i > low){
            i--;
            ok = 1;
            join(curr,i);
            low = min(low,l[curr]);
        }

        high = max(high,r[curr]);
        while(j < high){
            j++;
            ok = 1;
            join(curr,j);
            high = max(high,r[curr]);
        }

        if(!ok){
            i--;
            while(i>=0 && i==par[i])
                i--;

            j++;
            while(j<n && j==par[j])
                j++;

            if(i==-1 && j==n)break;
            if(i==-1 || j<n && low-i > j-high){
                /// go right (high)
                int nhigh = max(high,r[find(j)]);
                int nlow = min(low,l[find(j)]);
                int jj = j;
                while(j < nhigh){
                    j++;
                    nhigh = max(nhigh,r[find(j)]);
                    nlow = min(nlow,l[find(j)]);
                }
                if(i!=-1 && nlow == low){
                    ans += (low-i)*2;
                    join(curr,i);
                    j = high;
                }
                else{
                    j = jj;
                    ans += (j-high)*2;
                    join(curr,j);
                    i = low;
                }
            }
            else{
                assert(j==n || i>=0 && low-i < j-high);
                /// go left (low)
                int nhigh = max(high,r[find(i)]);
                int nlow = min(low,l[find(i)]);
                int ii = i;
                while(i > nlow){
                    i--;
                    nhigh = max(nhigh,r[find(i)]);
                    nlow = min(nlow,l[find(i)]);
                }
                if(j!=n && nhigh == high){
                    ans += (j-high)*2;
                    join(curr,j);
                    i = low;
                }
                else{
                    i = ii;
                    ans += (low-i)*2;
                    join(curr,i);
                    j = high;
                }
            }
        }
    }

    return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:103:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  103 |             if(i==-1 || j<n && low-i > j-high){
      |                         ~~~~^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from books.cpp:2:
books.cpp:126:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  126 |                 assert(j==n || i>=0 && low-i < j-high);
      |                                ~~~~~^~~~~~~~~~~~~~~~~

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