Submission #165056

#	Time	Username	Problem	Language	Result	Execution time	Memory
165056		sans	Doktor (COCI17_doktor)	C++14	100 / 100	245 ms	45356 KiB

doktor

#include <iostream>
#include <numeric>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

#define sp ' '
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(long long int yy = 0; yy < YY; ++yy)
#define prn(XX) cout << XX << endl
#define prs(XX) cout << XX << " "

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const int MOD = 1e9 + 7;
const int INF = 2e9 + 13;
const int mINF = -2e9 - 13;
const double PI = 3.14159265358979;
const double EPS = 1e-9;

vector<int> prefFixedPoints, perm;
vector<vector<int>> radii;
int N;

void precomputePrefixedPoints(void){
    for(int i = 1; i <= N; ++i)
        prefFixedPoints[i] = prefFixedPoints[i-1] + (perm[i] == i);
    return;
}

int fixedPointsInSegment(int left, int right){
    if(left > right) swap(left, right);
    return (prefFixedPoints[right] - prefFixedPoints[left-1]);
}

void findCenters(void){
    for(int i = 1; i <= N; ++i)
        radii[perm[i]+i].pb(abs(perm[i]-i));
    for(int i = 2; i <= N+N; ++i)
        sort(radii[i].begin(), radii[i].end());
    return;
}

void findBounds(int center, int radius, int &left, int &right){
    left = (center - radius)/2;
    right = (center + radius)/2;
    return;
}

void findBestCenter(void){
    int targetMax = mINF, targetLeft = -1, targetRight = -1;
    for(int center = 2;  center <= N+N; ++center){
        int createdFixedPoints = 0;
        for(auto radius: radii[center]){
            createdFixedPoints++;

            int left, right; findBounds(center, radius, left, right);
            int lostFixedPoints = fixedPointsInSegment(left, right);
            int res = createdFixedPoints - lostFixedPoints;

            if(res > targetMax){
                targetMax = res;
                targetLeft = left;
                targetRight = right;
            }
        }
    }

    cout << perm[targetLeft] << sp << perm[targetRight] << endl;
}

int main(int argc, char **argv){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    perm.resize(N+1); prefFixedPoints.assign(N+1, 0); radii.resize(2*N + 2);
    for(int i = 1; i <= N; ++i) cin >> perm[i];

    precomputePrefixedPoints();
    findCenters();
    findBestCenter();

    return 0;
}

//cikisir

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10