Submission #1239039

#TimeUsernameProblemLanguageResultExecution timeMemory
1239039vivkostov고대 책들 (IOI17_books)C++20
Compilation error
0 ms0 KiB
#pragma once
#include "grader.cpp"
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
    int l,r;
    long long int st;
};
bool cmp(cell a1,cell a2)
{
    return a1.l<a2.l;
}
int n,start,br,used[1000005],a[1000005],l[1005][1005],r[1005][1005];
long long int otg=0,dp[1005][1005];
cell p[1000005];
void dfs(int beg)
{
    p[br].l=min(p[br].l,beg);
    p[br].r=max(p[br].r,beg);
    p[br].st+=abs(a[beg]-beg);
    used[beg]=1;
    if(!used[a[beg]])
    {
        dfs(a[beg]);
    }
}
void prec()
{
    for(int i=1; i<=n; i++)
    {
        if(!used[i])
        {
            br++;
            p[br].l=1e9;
            dfs(i);
            otg+=p[br].st;
        }
    }
    sort(p+1,p+br+1,cmp);
    /*for(int i=1;i<=br;i++)
    {
        cout<<p[i].l<<" "<<p[i].r<<" "<<p[i].st<<endl;
    }*/
}
void resh()
{
    int to=1;
    for(int i=1; i<=n; i++)
    {
        if(p[i].l==p[i].r)continue;
        if(to>=p[i].l)
        {
            to=max(to,p[i].r);
        }
        else
        {
            otg+=(p[i].l-to)*2;
            to=p[i].r;
        }
    }
}
void make_dp()
{
    int mid=0;
    for(int i=1; i<=br; i++)
    {
        if(p[i].l<=start&&p[i].r>=start)
        {
            mid=i;
            break;
        }
    }
    if(p[mid].l!=p[mid].r)
    {
        for(int i=start; i>0; i--)
        {
            if(a[i]!=i)
            {
                dp[mid][mid]=start-i;
            }
        }
        for(int i=start+1; i<=n; i++)
        {
            if(a[i]!=i)
            {
                dp[mid][mid]=min(dp[mid][mid],(long long int)(i-start));
            }
        }
    }
    l[mid][mid]=p[mid].l;
    r[mid][mid]=p[mid].r;
    long long int dob=0;
    for(int i=mid; i>0; i--)
    {
        if(i!=mid)
        {
            l[i][mid]=min(l[i+1][mid],p[i].l);
            r[i][mid]=max(r[i+1][mid],p[i].r);
            if(l[i+1][mid]<=p[i].r)dp[i][mid]=dp[i+1][mid];
            else dp[i][mid]=dp[i+1][mid]+l[i+1][mid]-p[i].r;
            if(p[i].l!=p[i].r)dob=max(dob,dp[i][mid]);
        }
        for(int j=mid+1; j<=br; j++)
        {
            l[i][j]=min(l[i][j-1],p[j].l);
            r[i][j]=max(r[i][j-1],p[j].r);
            dp[i][j]=1e9;
            if(r[i][j-1]>=p[j].l)dp[i][j]=dp[i][j-1];
            else dp[i][j]=dp[i][j-1]+p[j].l-r[i][j-1];
            if(i!=mid)
            {
                if(l[i+1][j]<=p[i].r)dp[i][j]=min(dp[i][j],dp[i+1][j]);
                else dp[i][j]=min(dp[i][j],dp[i+1][j]+l[i+1][j]-p[i].r);
            }
            if((p[i].l!=p[i].r||i==mid)&&p[j].l!=p[j].r)dob=max(dob,dp[i][j]);
        }
    }
    otg+=dob*2;
}
long long minimum_walk(std::vector<int> p, int s)
{
    n=p.size();
    for(int i=1; i<=n; i++)
    {
        a[i]=p[i-1]+1;
    }
    start=s+1;
    prec();
    if(start)resh();
    else make_dp();
    return otg;
}

Compilation message (stderr)

books.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
/usr/bin/ld: /tmp/ccgyXd0a.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccgC1E9V.o:books.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status