81032024-01-12 13:27:54AblablablaRendező robot (80 pont)cpp17Wrong answer 4/80101ms15484 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int main(){
    int n;
    cin >> n;

    vector<int> szamok(n, 0);
    for(int i = 0; i < n; i++){
        cin >> szamok[i];
    }

    int db = 1;
    vector<pii> kezdok;
    vector<int> indexek(n, -1);
    kezdok.push_back({szamok[0], 0});
    for(int i = 1; i < n; i++){
        if(szamok[i] != szamok[i - 1] + 1){
            db++;
            kezdok.push_back({szamok[i], i});
        }
    }

    sort(kezdok.begin(), kezdok.end());

    for(int i = 0; i < kezdok.size(); i++){
        indexek[kezdok[i].second] = i;
    }

    vector<int> uj;
    int utolso = 0;
    vector<int> meretek(db, 0);
    for(int i = 0; i < n; i++){
        if(indexek[i] != -1){
            uj.push_back(indexek[i]);
            utolso = indexek[i];
        }
        meretek[utolso]++;
    }

    vector<bool> latta(db, 0);
    vector<int> minusz(db, 0);
    for(int i = 1; i < db; i++){
        if(latta[i - 1]){
            minusz[i] += meretek[i - 1];
        }
        latta[i] = 1;
    }

    latta.assign(db, 0);
    for(int i = db - 2; i >= 0; i--){
        if(latta[i + 1]){
            minusz[i] += meretek[i + 1];
        }
        latta[i] = 1;
    }

    for(int i = 0; i < db; i++){
        minusz[i] += meretek[i];
    }

    int maxi = 0;
    for(int i = 0; i < db; i++){
        maxi = max(maxi, minusz[i]);
    }

    cout << n - maxi << "\n";
}
SubtaskSumTestVerdictTimeMemory
base4/80
1Wrong answer0/03ms1940 KiB
2Accepted0/03ms2020 KiB
3Accepted2/23ms2248 KiB
4Wrong answer0/33ms2456 KiB
5Wrong answer0/33ms2564 KiB
6Wrong answer0/23ms2964 KiB
7Wrong answer0/23ms2916 KiB
8Wrong answer0/23ms3164 KiB
9Accepted2/23ms3216 KiB
10Wrong answer0/23ms3264 KiB
11Wrong answer0/23ms3260 KiB
12Wrong answer0/23ms3660 KiB
13Wrong answer0/23ms3620 KiB
14Wrong answer0/24ms3968 KiB
15Wrong answer0/23ms3924 KiB
16Wrong answer0/23ms3936 KiB
17Wrong answer0/23ms4052 KiB
18Wrong answer0/4101ms15168 KiB
19Wrong answer0/4101ms15396 KiB
20Wrong answer0/487ms11640 KiB
21Wrong answer0/471ms7312 KiB
22Wrong answer0/471ms7308 KiB
23Wrong answer0/472ms7700 KiB
24Wrong answer0/490ms12264 KiB
25Wrong answer0/4101ms15484 KiB
26Wrong answer0/476ms8832 KiB
27Wrong answer0/496ms14612 KiB
28Wrong answer0/478ms9584 KiB
29Wrong answer0/476ms9064 KiB