Submission #473662

# Submission time Handle Problem Language Result Execution time Memory
473662 2021-09-15T19:58:48 Z MamdouhN Doktor (COCI17_doktor) C++17
80 / 100
866 ms 77696 KB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

map<pair<int,int>,int>idk;
map<pair<int,int>,pair<int,int>>k;

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    int ar[n];
    int doingnothing=0;
    vector<int>lol;
    lol.push_back(0);
    for(int i=0;i<n;i++)
    {
        cin>>ar[i];
        if(ar[i]==i+1)doingnothing++;
        int x = min(ar[i]-1,i);
        int y = max(ar[i]-1,i);
        int dist = min(x - 0 , n - y-1);
        //cout<<x-dist<<" "<<y+dist<<endl;
        idk[{ x-dist , y+dist }]++;
        if(y>k[{ x-dist , y+dist }].second)k[{ x-dist , y+dist }] = {x,y};
        lol.push_back(doingnothing);
    }
    int x = 0;
    pair<int,int>ans;
    for(auto v:idk)
    {
        int st = k[{v.first.first,v.first.second}].first;
        int en = k[{v.first.first,v.first.second}].second;
        int z = lol[en+1] - lol[st];
        if((en-st+1)%2)
        {
            if(ar[(en+st)/2] = ((en+st)/2)+1)z--;
        }
        if(v.second-z> x)
        {
            x = v.second;
            ans = {st,en};
        }
    }
    cout<<ar[ans.first]<<" "<<ar[ans.second]<<endl;
}




Compilation message

doktor.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main()
      | ^~~~
doktor.cpp: In function 'int main()':
doktor.cpp:41:30: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   41 |             if(ar[(en+st)/2] = ((en+st)/2)+1)z--;
      |                ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 844 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 8 ms 1488 KB Output is correct
2 Correct 38 ms 8484 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 11492 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 866 ms 60540 KB Output is correct
2 Correct 62 ms 9908 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 429 ms 36312 KB Output is correct
2 Correct 522 ms 77696 KB Output is correct