oj.uz

Submission #491396

# Submission time Handle Problem Language Result Execution time Memory
491396 2021-12-01T23:37:06 Z Yazan_Alattar Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 243 ms 50564 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 1000001;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int n, k, a[M];
vector <int> pos[M];

void out(int j)
{
    if(k == 0 || j == 0){
        cout << j << " ";
        return;
    }
    --k;
    out(j - 1);
    out(j - 1);
    return;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k;
    vector < pair <int,int> > v(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        v[i] = {a[i], i};
    }
    for(int j = 0; j < 30; ++j){
        vector < pair <int,int> > nw;
        int cur = 0;
        for(int i = 0; i < v.size(); ++i){
            if(cur){
                if(nw.back().F != v[i].F){
                    int last = nw.back().S;
                    pos[nw.back().S].pb(j);
                    nw.pop_back();
                    nw.pb({j + 1, last});
                    nw.pb(v[i]);
                    --k;
                }
                else{
                    nw.pop_back();
                    nw.pb({j + 1, v[i].S});
                }
                cur = 0;
            }
            else{
                nw.pb(v[i]);
                cur += (v[i].F == j);
            }
        }
        if(cur){
            --k;
            nw.pop_back();
            nw.pb({j + 1, v.back().S});
            pos[nw.back().S].pb(j);
        }
        v = nw;
    }
    int cur = 0;
    for(int i = 0; i < n; ++i){
        cout << a[i] << " ";
        for(auto j : pos[i]) out(j);
    }
    cout << endl;
    return 0;
}
// Don't forget special cases. (n = 1?)
// Look for the constraints. (Runtime array? overflow?)

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i = 0; i < v.size(); ++i){
      |                        ~~^~~~~~~~~~
zalmoxis.cpp:82:9: warning: unused variable 'cur' [-Wunused-variable]
   82 |     int cur = 0;
      |         ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 50080 KB Output is correct
2 Correct 186 ms 50448 KB Output is correct
3 Correct 198 ms 50288 KB Output is correct
4 Correct 183 ms 50288 KB Output is correct
5 Correct 199 ms 50316 KB Output is correct
6 Correct 187 ms 49972 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 50208 KB Output is correct
2 Correct 176 ms 49928 KB Output is correct
3 Correct 194 ms 50436 KB Output is correct
4 Correct 206 ms 50484 KB Output is correct
5 Correct 186 ms 50320 KB Output is correct
6 Correct 187 ms 50228 KB Output is correct
7 Correct 243 ms 50344 KB Output is correct
8 Correct 198 ms 50564 KB Output is correct
9 Correct 202 ms 49460 KB Output is correct
10 Correct 130 ms 35824 KB Output is correct
11 Correct 160 ms 39932 KB Output is correct
12 Correct 90 ms 25672 KB Output is correct
13 Correct 93 ms 25724 KB Output is correct
14 Correct 104 ms 25672 KB Output is correct