Submission #116932

#	Time	Username	Problem	Language	Result	Execution time	Memory
116932		souhhcong	Doktor (COCI17_doktor)	C++14	100 / 100	367 ms	44680 KiB

doktor

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define st first
#define nd second
const int N = 5e5+5;
int n, a[N];
int center[N];
int pref[N];
vector<pair<int,int> > seg[2*N];
int mx = -N;
pair<int,int> ans;
int cnt = 0;

int main()
{
//    freopen("Doktor.inp","r",stdin);
//    freopen("Doktor.out","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] == i)
        {
            cnt++;
        }
        pref[i] = cnt;
        center[i] = a[i]+i;
        if (a[i] < i)
            seg[center[i]].push_back({a[i],i});
        else
            seg[center[i]].push_back({i,a[i]});
    }
    for (int i = 1; i <= 2*n; i++)
    {
        if (seg[i].size() == 0) continue;
        int tmp = 0;
        sort(seg[i].begin(),seg[i].end(), greater<pair<int,int> >() );
        for (int j = 0; j < seg[i].size(); j++)
        {
            int L = seg[i][j].st, R = seg[i][j].nd;
//            tmp++;
//            tmp -= (pref[R] - pref[L-1]);
            tmp = (j+1) - (pref[R] - pref[L-1]);
            if (tmp > mx)
            {
                mx = tmp;
                ans = seg[i][j];
            }
        }

    }
    cout << a[ans.st] << ' ' << a[ans.nd];

}

Compilation message (stderr)

doktor.cpp: In function 'int main()':
doktor.cpp:41:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < seg[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~

• 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