oj.uz

Submission #374370

# Submission time Handle Problem Language Result Execution time Memory
374370 2021-03-07T08:25:27 Z Atill83 Doktor (COCI17_doktor) C++14
100 / 100
 250 ms 46060 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 5e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
int a[MAXN];
vector<int> deg[2*MAXN];
int pre[MAXN];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n;

    for(int i = 1; i <= n; i++){
        cin>>a[i];
        deg[i + a[i]].push_back(i);
        pre[i] = pre[i - 1] + (a[i] == i);
    }

    pii ans;
    int mx = -1;

    for(int i = 1; i <= n; i++){
        int l = i, r = a[i];
        if(r < l)
            swap(l, r);

        int df = (upper_bound(deg[l + r].begin(), deg[l + r].end(), r) - lower_bound(deg[l + r].begin(), deg[l + r].end(), l)) - (pre[r] - pre[l - 1]);

        if((r - l + 1) % 2){
            if(a[(r + l) / 2] == (r + l) / 2)
                df++;
        }
        if(df > mx){
            ans = {l, r};
            mx = df;
        }
    }

    cout<<a[ans.ff]<<" "<<a[ans.ss]<<endl;
    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 19 ms 23788 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 18 ms 23916 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24044 KB Output is correct
2 Correct 18 ms 23916 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23916 KB Output is correct
2 Correct 17 ms 23788 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24300 KB Output is correct
2 Correct 89 ms 30056 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 27116 KB Output is correct
2 Correct 39 ms 25728 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 42312 KB Output is correct
2 Correct 132 ms 33120 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 34668 KB Output is correct
2 Correct 97 ms 46060 KB Output is correct