Submission #835301

#	Time	Username	Problem	Language	Result	Execution time	Memory
835301		oscar1f	Ancient Books (IOI17_books)	C++17	70 / 100	178 ms	110224 KiB

books

#include<bits/stdc++.h>
#include "books.h"

using namespace std;
using ll=long long;

const ll MAX_TAILLE=1000*1000+5,MAX_MEMO=1000+5,DECA=(1<<10),INFINI=1000*1000*1000;
ll nbVal,rep,posDeb,nbCompo,debInter,finInter,maxFin;
vector<ll> obj,listeCompo;
ll idCompo[MAX_TAILLE],finCompo[MAX_TAILLE],tailleCompo[MAX_TAILLE],debCompo[MAX_TAILLE];
ll arbreMin[2*DECA],arbreMax[2*DECA];
ll memo[MAX_MEMO][MAX_MEMO];

void DFS(ll pos) {
	if (idCompo[pos]==0) {
		idCompo[pos]=nbCompo;
		tailleCompo[nbCompo]++;
		DFS(obj[pos]);
	}
}

ll calcMin(ll deb,ll fin) {
    if (deb==fin) {
        return arbreMin[deb];
    }
    if (deb%2==1) {
        return min(arbreMin[deb],calcMin(deb+1,fin));
    }
    if (fin%2==0) {
        return min(arbreMin[fin],calcMin(deb,fin-1));
    }
    return calcMin(deb/2,fin/2);
}

ll calcMax(ll deb,ll fin) {
    if (deb==fin) {
        return arbreMax[deb];
    }
    if (deb%2==1) {
        return max(arbreMax[deb],calcMax(deb+1,fin));
    }
    if (fin%2==0) {
        return max(arbreMax[fin],calcMax(deb,fin-1));
    }
    return calcMax(deb/2,fin/2);
}

ll dyna(ll deb,ll fin) {
    if (deb<=debInter and fin>=finInter) {
        return 0;
    }
    if (memo[deb][fin]!=-1) {
        return memo[deb][fin];
    }
    memo[deb][fin]=INFINI;
    if (fin<nbVal-1) {
        if (calcMax(DECA+deb,DECA+fin)>fin) {
            memo[deb][fin]=min(memo[deb][fin],dyna(deb,fin+1));
        }
        else {
            memo[deb][fin]=min(memo[deb][fin],dyna(deb,fin+1)+2);
        }
    }
    if (deb>0) {
        if (calcMin(DECA+deb,DECA+fin)<deb) {
            memo[deb][fin]=min(memo[deb][fin],dyna(deb-1,fin));
        }
        else {
            memo[deb][fin]=min(memo[deb][fin],dyna(deb-1,fin)+2);
        }
    }
    return memo[deb][fin];
}

ll minimum_walk(vector<int> p, int s) {
	posDeb=s;
	nbVal=p.size();
	for (auto i:p) {
		obj.push_back(i);
	}
	for (ll i=nbVal-1;i>=0;i--) {
		if (idCompo[i]==0) {
			nbCompo++;
			DFS(i);
            finCompo[nbCompo]=i;
		}
        debCompo[idCompo[i]]=i;
		rep+=abs(i-obj[i]);
	}
	finInter=nbVal-1;
	while (finInter>=0 and tailleCompo[idCompo[finInter]]==1) {
		finInter--;
	}
    debInter=0;
    while (debInter<=nbVal-1 and tailleCompo[idCompo[debInter]]==1) {
        debInter++;
    }
    if (posDeb==0) {
        ll pos=0;
        while (pos<finInter) {
            maxFin=max(maxFin,finCompo[idCompo[pos]]);
            if (maxFin==pos) {
                rep+=2;
            }
            pos++;
        }
        return rep;
    }
    for (ll i=0;i<MAX_MEMO;i++) {
        for (ll j=0;j<MAX_MEMO;j++) {
            memo[i][j]=-1;
        }
    }
    for (ll i=0;i<2*DECA;i++) {
        arbreMin[i]=INFINI;
        arbreMax[i]=-INFINI;
    }
    for (ll i=0;i<nbVal;i++) {
        arbreMin[DECA+i]=debCompo[idCompo[i]];
        arbreMax[DECA+i]=finCompo[idCompo[i]];
    }
    for (ll i=DECA-1;i>0;i--) {
        arbreMin[i]=min(arbreMin[2*i],arbreMin[2*i+1]);
        arbreMax[i]=max(arbreMax[2*i],arbreMax[2*i+1]);
    }
    return rep+dyna(posDeb,posDeb);
}

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