oj.uz

Submission #165056

# Submission time Handle Problem Language Result Execution time Memory
165056 2019-11-24T20:56:40 Z sans Doktor (COCI17_doktor) C++14
100 / 100
 245 ms 45356 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 552 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1144 KB Output is correct
2 Correct 92 ms 20976 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7928 KB Output is correct
2 Correct 30 ms 7028 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 41708 KB Output is correct
2 Correct 157 ms 33268 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 24672 KB Output is correct
2 Correct 128 ms 45356 KB Output is correct