답안 #133599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133599	2019-07-21T06:07:50 Z	forelax	Kralj (COCI16_kralj)	C++14	140 / 140	1446 ms	72752 KB

kralj

#include<bits/stdc++.h>
using namespace std;
int n,rez=0;
vector<int> a,p,v;
inline void solve(vector<int>& A,vector<vector<int> >& B){
    int N=A.size();
    set<int> s;
    for(int i = 0 ; i < N ; i ++){
        for(int j = 0 ; j < B[i].size() ; j ++)
            s.insert(v[B[i][j]]);
        if(s.upper_bound(A[i])==s.end()){
            s.erase(s.begin());
        }else{
            s.erase(s.upper_bound(A[i]));
            rez++;
        }
    }
}
int main(){
    cin>>n;
    a.resize(n);
    p.resize(n);
    v.resize(n);
    vector<int> hs(2*n);
    vector<vector<int> > cmp(n);
    for(int i = 0 ; i < n ; i ++){
        cin>>a[i];
        a[i]--;
        hs[a[i]]++;
        hs[n+a[i]]++;
        cmp[a[i]].push_back(i);
    }
    for(int i = 0 ; i < n ; i ++)
        cin>>p[i];
    for(int i = 0 ; i < n ; i ++)
        cin>>v[i];
    int ml=0;
    int ps=-1;
    for(int i = 0 ; i < hs.size() ; i ++){
        if(hs[i]){
            int j=i;
            int c=hs[i];
            while(c){
                c--;
                if(c&&j+1<hs.size()){
                    j++;
                    c+=hs[j];
                }
            }
            int l=j-i+1;
            if(l>ml){
                ml=l;
                ps=i;
            }
            i=j;
        }
    }
    for(int i = ps ; i < ps+n ; i ++){
        if(hs[i]){
            int j=i;
            int c=hs[i];
            vector<int> fv;
            vector<vector<int> > g;
            while(c){
                fv.push_back(p[j%n]);
                g.push_back(cmp[j%n]);
                c--;
                if(c&&j+1<hs.size()){
                    j++;
                    c+=hs[j];
                }
            }
            solve(fv,g);
            i=j;
        }
    }
    cout<<rez;
}

Compilation message

kralj.cpp: In function 'void solve(std::vector<int>&, std::vector<std::vector<int> >&)':
kralj.cpp:9:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0 ; j < B[i].size() ; j ++)
                         ~~^~~~~~~~~~~~~
kralj.cpp: In function 'int main()':
kralj.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < hs.size() ; i ++){
                     ~~^~~~~~~~~~~
kralj.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(c&&j+1<hs.size()){
                       ~~~^~~~~~~~~~
kralj.cpp:68:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(c&&j+1<hs.size()){
                       ~~~^~~~~~~~~~

Subtask #1

140.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1446 ms	59340 KB	Output is correct
2	Correct	1122 ms	57420 KB	Output is correct
3	Correct	1408 ms	71436 KB	Output is correct
4	Correct	1414 ms	72752 KB	Output is correct
5	Correct	1247 ms	50304 KB	Output is correct
6	Correct	1137 ms	50056 KB	Output is correct
7	Correct	1375 ms	58260 KB	Output is correct
8	Correct	1182 ms	54164 KB	Output is correct
9	Correct	1439 ms	61128 KB	Output is correct
10	Correct	1277 ms	53852 KB	Output is correct