oj.uz

Submission #381385

# Submission time Handle Problem Language Result Execution time Memory
381385 2021-03-25T07:14:33 Z IldarKA Doktor (COCI17_doktor) C++14
100 / 100
 793 ms 57068 KB 
#include <bits/stdc++.h>

using namespace std;
int n, a[500001], pref[500001];
map < pair < int, int >, vector < pair < int, int > > > m;
int get_sum(int l, int r){
    if((r - l) % 2 == 0){
        return pref[r] - pref[l - 1] - int(a[(r + l) / 2] == (r + l) / 2);
    }
    else{
        return pref[r] - pref[l - 1];
    }
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        int len = abs(a[i] - i);
        m[{(len + 1) / 2 + min(a[i], i), max(a[i], i) - (len + 1) / 2}].push_back({min(a[i], i), max(a[i], i)});
        pref[i] += pref[i - 1] + int(a[i] == i);
    }
    int l = 1, r = 1;
    int mx = pref[n];
    for(auto it : m){
        sort(it.second.begin(), it.second.end());
        int kol = (int)it.second.size();
        for(int i = 0; i < it.second.size(); i++){
            int san = get_sum(it.second[i].first, it.second[i].second);
            if(pref[n] - san + kol > mx){
                mx = pref[n] - san + kol;
                l = it.second[i].first;
                r = it.second[i].second;
            }
            kol--;
        }
    }
    cout << a[l] << " " << a[r];
}

Compilation message

doktor.cpp: In function 'int main()':
doktor.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int i = 0; i < it.second.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 748 KB Output is correct
2 Correct 2 ms 492 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1280 KB Output is correct
2 Correct 135 ms 7512 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 8300 KB Output is correct
2 Correct 43 ms 3424 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 44212 KB Output is correct
2 Correct 228 ms 12168 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 25964 KB Output is correct
2 Correct 341 ms 57068 KB Output is correct