제출 #1155885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155885		alexdd	고대 책들 (IOI17_books)	C++20	22 / 100	2097 ms	19784 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
int p[1000005];
int maxpref[1000005],minsuff[1000005];
bool br[1000005],br2[1000005];
long long minimum_walk(std::vector<int> cit_p, int s)
{
    s++;
    n = cit_p.size();
    for(int i=1;i<=n;i++)
        p[i] = cit_p[i-1]+1;

    int ult=0,primu=n+1;
    long long rez=0;
    for(int i=1;i<=n;i++)
    {
        maxpref[i] = max(maxpref[i-1], p[i]);
        if(p[i]!=i)
        {
            ult=i;
            primu = min(primu, i);
        }
        rez += abs(p[i]-i);
    }
    minsuff[n+1] = n+1;
    for(int i=n;i>0;i--)
        minsuff[i] = min(minsuff[i+1], p[i]);

    if(ult==0)
        return 0;

    ult = max(ult, s);
    primu = min(primu, s);

    for(int i=primu+1;i<=ult;i++)
        if(maxpref[i-1]<i && minsuff[i]>=i)
            br[i]=1;

    for(int i=primu+1;i<=s;i++)
    {
        bool gasit=0;
        for(int j=1;j<i;j++)
            if(i<=p[j] && p[j]<=s)
                gasit=1;
        for(int j=i;j<=s;j++)
            if(p[j]<i)
                gasit=1;
        if(!gasit)
            br2[i]=1;
    }
    for(int i=s+1;i<=ult;i++)
    {
        bool gasit=0;
        for(int j=i;j<=n;j++)
            if(s<=p[j] && p[j]<i)
                gasit=1;
        for(int j=s;j<i;j++)
            if(p[j]>=i)
                gasit=1;
        if(!gasit)
            br2[i]=1;
    }

    int tole=s,tori=s;
    while(tole-1>=1 && !br[tole])
        tole--;
    while(tori+1<=n && !br[tori+1])
        tori++;

    int tole2=s,tori2=s;
    while(tole2-1>=1 && !br2[tole2])
        tole2--;
    while(tori2+1<=n && !br2[tori2+1])
        tori2++;

    //rez += 2*min(tori-tori2, tole2-tole);
    
    int cntri2=0,cntri=0;
    for(int i=s+1;i<=n;i++)
    {
        if(br2[i])
            cntri2++;
        if(br[i])
            cntri++;
    }
    int cntle2=0,cntle=0;
    for(int i=2;i<=s;i++)
    {
        if(br2[i])
            cntle2++;
        if(br[i])
            cntri++;
    }

    rez += min(cntle + cntri2, cntri + cntle2)*2;


    return rez;
}

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