답안 #485388

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
485388 2021-11-07T14:57:49 Z Habitus Kralj (COCI16_kralj) C++14
140 / 140
566 ms 68104 KB
#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++) {
      |                      ~~~^~
# 결과 실행 시간 메모리 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