oj.uz

Submission #68515

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

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:10: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:12: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 482 ms 69088 KB Output is correct
2 Correct 470 ms 69204 KB Output is correct
3 Correct 482 ms 69300 KB Output is correct
4 Correct 549 ms 69300 KB Output is correct
5 Correct 522 ms 69300 KB Output is correct
6 Correct 482 ms 69380 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 69380 KB Output is correct
2 Correct 458 ms 69380 KB Output is correct
3 Correct 498 ms 69380 KB Output is correct
4 Correct 434 ms 69380 KB Output is correct
5 Correct 513 ms 69380 KB Output is correct
6 Correct 448 ms 69408 KB Output is correct
7 Correct 455 ms 69408 KB Output is correct
8 Correct 525 ms 69408 KB Output is correct
9 Correct 449 ms 69408 KB Output is correct
10 Correct 299 ms 69408 KB Output is correct
11 Correct 371 ms 69408 KB Output is correct
12 Correct 153 ms 69408 KB Output is correct
13 Correct 159 ms 69408 KB Output is correct
14 Correct 249 ms 69408 KB Output is correct