답안 #195599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
195599	2020-01-16T15:34:55 Z	stefdasca	Kralj (COCI16_kralj)	C++14	56 / 140	856 ms	47448 KB

kralj

#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

int n, rival[500002];

int frq[500002], sp[1000002];

vector<int> enemy[500002];
int skill[500002], skill2[500002];

int ans = 0;
vector<int> va, vb;

int solve(int st)
{
    int ss = 0;
    int dif = 0;
    for(int i = st; i <= st + n - 1; ++i)
    {
        dif--;
        va.pb(skill[i - (i > n) * n]);
        for(int j = 0; j < enemy[i - (i > n) * n].size(); ++j)
            vb.pb(skill2[enemy[i - (i > n) * n][j]]), ++dif;
        if(dif == 0)
        {
            sort(va.begin(), va.end());
            sort(vb.begin(), vb.end());
            int pa = 0;
            for(int j = 0; j < va.size(); ++j)
            {
                while(pa < vb.size() && vb[pa] < va[j])
                    ++pa;
                if(pa < vb.size())
                    ++ss, ++pa;
                else
                    break;
            }
            va.clear();
            vb.clear();
            if(ss + (st + n - 1) - i <= ans)
                return ss;
        }
    }
    return ss;
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> rival[i], ++frq[rival[i]], enemy[rival[i]].pb(i);
    for(int i = 1; i <= n; ++i)
        cin >> skill[i];
    for(int i = 1; i <= n; ++i)
        cin >> skill2[i];
    deque<int> mn;
    for(int i = 1; i < 2 * n; ++i)
    {
        sp[i] = sp[i-1] + frq[i - n * (i > n)] - 1;
        if(i > n && !mn.empty() && mn[0] == i - n)
            mn.pop_front();
        while(!mn.empty() && sp[i] < sp[mn.back()])
            mn.pop_back();
        mn.pb(i);
        if(i >= n && sp[mn[0]] >= sp[i - n])
            ans = max(ans, solve(i - n + 1));
    }
    cout << ans;
    return 0;
}

Compilation message

kralj.cpp: In function 'int solve(int)':
kralj.cpp:36:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < enemy[i - (i > n) * n].size(); ++j)
                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kralj.cpp:43:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < va.size(); ++j)
                            ~~^~~~~~~~~~~
kralj.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(pa < vb.size() && vb[pa] < va[j])
                       ~~~^~~~~~~~~~~
kralj.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(pa < vb.size())
                    ~~~^~~~~~~~~~~

Subtask #1

56.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	262 ms	33380 KB	Output is correct
2	Correct	233 ms	32436 KB	Output is correct
3	Correct	299 ms	37392 KB	Output is correct
4	Correct	313 ms	37560 KB	Output is correct
5	Incorrect	400 ms	41704 KB	Output isn't correct
6	Incorrect	436 ms	41364 KB	Output isn't correct
7	Incorrect	856 ms	45660 KB	Output isn't correct
8	Incorrect	554 ms	42824 KB	Output isn't correct
9	Incorrect	647 ms	47448 KB	Output isn't correct
10	Incorrect	466 ms	43896 KB	Output isn't correct