oj.uz

Submission #68514

# Submission time Handle Problem Language Result Execution time Memory
68514 2018-08-17T08:51:13 Z Bruteforceman Zalmoxis (BOI18_zalmoxis) C++11
100 / 100
 571 ms 69448 KB 
#include <bits/stdc++.h>
using namespace std;
int a[1000010];
vector <int> v[1000010];
int alive[1000010];

struct data {
    int val, idx;
    data (int val, int idx) : val(val), idx(idx) {}
    data () {}
    bool operator < (data p) const {
        if(val == p.val) return idx < p.idx;
        return val > p.val;
    }
};

int main(int argc, char const *argv[])
{
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        alive[i] = 1;
        v[i].emplace_back(a[i]);
    }  
    int sz = n;
    vector <int> can;
    for(int i = 0; i < 30; i++) {
        can.clear();
        for(int j = 1; j <= n; j++) {
            if(alive[j]) can.emplace_back(j);
        }
        int size = can.size();
        for(int j = size - 1; j >= 0 && sz <= (n + k); j--) {
            if(alive[can[j]] == 0) continue;
            if(a[can[j]] == i) {
                if(j == 0 || a[can[j - 1]] != i) {
                    v[can[j]].emplace_back(i);
                    ++a[can[j]];
                    ++sz;
                } else {
                    alive[can[j - 1]] = 0;
                    ++a[can[j]];
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        vector <int> tmp;
        while(v[i].size() > 1 && sz < n + k) {
            if(v[i].back() > 0) {
                int x = v[i].back();
                v[i].pop_back();
                v[i].emplace_back(x - 1);
                v[i].emplace_back(x - 1);
                ++sz;   
            } else {
                v[i].pop_back();
                tmp.emplace_back(0);
            }
        }
        for(auto j : tmp) {
            v[i].emplace_back(j);
        }
        for(auto j : v[i]) {
            printf("%d ", j);
        }
    }
    printf("\n");
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main(int, const char**)':
zalmoxis.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
zalmoxis.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 68960 KB Output is correct
2 Correct 561 ms 69292 KB Output is correct
3 Correct 481 ms 69292 KB Output is correct
4 Correct 487 ms 69292 KB Output is correct
5 Correct 463 ms 69300 KB Output is correct
6 Correct 457 ms 69424 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 69424 KB Output is correct
2 Correct 510 ms 69424 KB Output is correct
3 Correct 508 ms 69424 KB Output is correct
4 Correct 440 ms 69424 KB Output is correct
5 Correct 459 ms 69424 KB Output is correct
6 Correct 434 ms 69424 KB Output is correct
7 Correct 524 ms 69424 KB Output is correct
8 Correct 571 ms 69448 KB Output is correct
9 Correct 460 ms 69448 KB Output is correct
10 Correct 317 ms 69448 KB Output is correct
11 Correct 421 ms 69448 KB Output is correct
12 Correct 137 ms 69448 KB Output is correct
13 Correct 140 ms 69448 KB Output is correct
14 Correct 147 ms 69448 KB Output is correct