oj.uz

Submission #747508

# Submission time Handle Problem Language Result Execution time Memory
747508 2023-05-24T08:40:47 Z vjudge1 Kralj (COCI16_kralj) C++17
84 / 140
 581 ms 92084 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+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
84.0 / 140.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 78652 KB Execution killed with signal 6
2 Runtime error 284 ms 77240 KB Execution killed with signal 6
3 Runtime error 352 ms 90436 KB Execution killed with signal 6
4 Runtime error 350 ms 92084 KB Execution killed with signal 6
5 Correct 480 ms 43812 KB Output is correct
6 Correct 436 ms 43972 KB Output is correct
7 Correct 553 ms 47904 KB Output is correct
8 Correct 460 ms 45104 KB Output is correct
9 Correct 581 ms 49908 KB Output is correct
10 Correct 522 ms 47308 KB Output is correct