Submission #80909

#	Time	Username	Problem	Language	Result	Execution time	Memory
80909		ngot23	Doktor (COCI17_doktor)	C++11	100 / 100	271 ms	46716 KiB

doktor

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=500001;
int a[N*2], n, f[N*2];
vector <int > center[N*2];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    cin >> n;
    rep(i, 1, n) {
        int u;
        cin >> u;
        int ii=2*i-1;
        if(u==i) f[ii]=1;
        int xx=2*u-1;
        int c=(xx+ii)/2;
        center[c].push_back(abs(c-ii));
        a[ii]=u;
    }
    rep(i, 1, n*2-1) f[i]+=f[i-1];

    int lef, rig, ans=0;
    rep(i, 2, n*2-1) {
        if(center[i].size()==0) continue;
        sort(center[i].begin(), center[i].end());
        rep(j, 0, center[i].size()-1) {
            int r=center[i][j];
            int xx=f[i-r-1]+f[n*2-1]-f[i+r]+j+1;
            if(xx>ans) {
                ans=xx;
                lef=a[i-r], rig=a[i+r];
            }
        }
    }
    cout << lef << ' ' << rig;
    return 0;
}

Compilation message (stderr)

doktor.cpp: In function 'int main()':
doktor.cpp:2:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
                                       ^
doktor.cpp:30:9: note: in expansion of macro 'rep'
         rep(j, 0, center[i].size()-1) {
         ^~~
doktor.cpp:39:24: warning: 'rig' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout << lef << ' ' << rig;
     ~~~~~~~~~~~~~~~~~~~^~~~~~
doktor.cpp:39:20: warning: 'lef' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout << lef << ' ' << rig;
                    ^~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10