Submission #747508

#	Time	Username	Problem	Language	Result	Execution time	Memory
747508		vjudge1	Kralj (COCI16_kralj)	C++17	84 / 140	581 ms	92084 KiB

kralj

#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+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 (stderr)

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: 84 / 140