Submission #485388

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
485388	2021-11-07T14:57:49 Z	Habitus	Kralj (COCI16_kralj)	C++14	140 / 140	566 ms	68104 KB

kralj

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n, a[500002], p[500002], v[500002], kolko[500002];
set<int> s[500002];
int main() {
    ios;
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        kolko[a[i]]++;
    }
    for(int i=1; i<=n; i++) cin >> p[i];
    for(int i=1; i<=n; i++) {
        cin >> v[i];
        s[a[i]].insert(v[i]);
    }
    int maxi=0, tren=0;
    for(int i=n; i>=1; i--) {
        tren+=kolko[i]-1;
        maxi=max(maxi, tren);
    }
    int taj;
    if(maxi<=0) {
        taj=1;
    }
    else {
        for(int i=1; i<n; i++) {
            maxi+=kolko[i]-1;
            if(maxi<=0) {
                taj=i+1;
                break;
            }
        }
    }
    tren=taj;
    int uk=0;
    for(int i=taj; i<taj+n; i++) {
        int ii=(i-1)%n+1;
        if(sz(s[ii])>sz(s[tren])) {
            for(auto x:s[tren]) s[ii].insert(x);
            tren=ii;
        }
        else if(tren!=ii) {
            for(auto x:s[ii]) s[tren].insert(x);
        }
        auto it=s[tren].lower_bound(p[ii]);
        if(it==s[tren].end()) s[tren].erase(s[tren].begin());
        else {
            uk++;
            s[tren].erase(it);
        }
    }
    cout << uk;
    return 0;
}

Compilation message

kralj.cpp: In function 'int main()':
kralj.cpp:34:17: warning: 'tren' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |     int maxi=0, tren=0;
      |                 ^~~~
kralj.cpp:54:13: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     for(int i=taj; i<taj+n; i++) {
      |             ^
kralj.cpp:54:25: warning: 'taj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     for(int i=taj; i<taj+n; i++) {
      |                      ~~~^~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	502 ms	55852 KB	Output is correct
2	Correct	329 ms	54716 KB	Output is correct
3	Correct	396 ms	62244 KB	Output is correct
4	Correct	418 ms	62788 KB	Output is correct
5	Correct	524 ms	64104 KB	Output is correct
6	Correct	451 ms	63252 KB	Output is correct
7	Correct	434 ms	65592 KB	Output is correct
8	Correct	362 ms	61252 KB	Output is correct
9	Correct	453 ms	68104 KB	Output is correct
10	Correct	566 ms	67320 KB	Output is correct