oj.uz

Submission #747510

# Submission time Handle Problem Language Result Execution time Memory
747510 2023-05-24T08:44:45 Z vjudge1 Kralj (COCI16_kralj) C++17
140 / 140
 741 ms 49744 KB 
#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 1000007
#define INF 90000000000000000
//#define ll long long
///#define cin fin
///#define cout fout
#define fi first
#define se second
using namespace std;
double const EPS = 1e-14;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
const int Max = 5e5 + 5;
vector<int> vv[Max];
int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n; cin >> n; int a[n+1], p[n+1], v[n+1], cnt[n+1] = {}, start, ans = 0; set<int> st;

    for(int i = 1; i <= n; i++) st.insert(i);
    for(int i = 1; i <= n; i++) { cin >> a[i]; cnt[a[i]]++; }
    for(int i = 1; i <= n; i++) cin >> p[i];
    for(int i = 1; i <= n; i++) { cin >> v[i]; vv[a[i]].push_back(v[i]);}
    /*for(int i = 1; i <= n; i++) {
        cout << i << ' ' << cnt[i] << 'k' << endl;
        for(auto j : vv[i]) {
            cout << j << ' ';
        }
        cout << 'j' << endl;
    }*/
    for(int i = n; i >= 1; i--) {
        auto j = st.lower_bound(i);
        while(cnt[i]--) {
            if(j == st.end()) j = st.begin();
            int x = *j; j++;
            if(st.size() == 1) start = (x%n)+1;
            st.erase(x);
        }
    }
    //cout << start << 's' << endl;
    for(int i = 0; i < n; i++) {
        for(auto j : vv[start]) {
            st.insert(j);
        }
        if(st.empty()) assert(false);
        auto indx = st.upper_bound(p[start]);
        if(indx == st.end()) indx = st.begin();
        else ans++;
        st.erase(*indx);
        start%= n;
        start++;
    }
    cout << ans;
    return 0;
}

Compilation message

kralj.cpp: In function 'int main()':
kralj.cpp:20:65: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |     int n; cin >> n; int a[n+1], p[n+1], v[n+1], cnt[n+1] = {}, start, ans = 0; set<int> st;
      |                                                                 ^~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 39340 KB Output is correct
2 Correct 519 ms 38644 KB Output is correct
3 Correct 599 ms 44768 KB Output is correct
4 Correct 610 ms 45516 KB Output is correct
5 Correct 494 ms 43740 KB Output is correct
6 Correct 445 ms 44160 KB Output is correct
7 Correct 579 ms 47756 KB Output is correct
8 Correct 453 ms 45008 KB Output is correct
9 Correct 584 ms 49744 KB Output is correct
10 Correct 558 ms 47348 KB Output is correct