oj.uz

Submission #491391

# Submission time Handle Problem Language Result Execution time Memory
491391 2021-12-01T23:24:34 Z Yazan_Alattar Zalmoxis (BOI18_zalmoxis) C++14
85 / 100
 203 ms 50492 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 = 1000007;
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];

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]){
            if(k > 0){
                cout << j - 1 << " ";
                --k;
                int cur = j - 1;
                while(k > 0){
                    if(cur == 1) break;
                    cout << --cur << " ";
                    --k;
                }
                cout << cur << " ";
            }
            else cout << 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:41: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]
   41 |         for(int i = 0; i < v.size(); ++i){
      |                        ~~^~~~~~~~~~
zalmoxis.cpp:70:9: warning: unused variable 'cur' [-Wunused-variable]
   70 |     int cur = 0;
      |         ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 50188 KB Output is correct
2 Correct 197 ms 50388 KB Output is correct
3 Correct 202 ms 50352 KB Output is correct
4 Correct 186 ms 50260 KB Output is correct
5 Correct 197 ms 50316 KB Output is correct
6 Correct 189 ms 49972 KB Output is correct

Subtask #2
55.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 50176 KB Output is correct
2 Correct 203 ms 49916 KB Output is correct
3 Correct 189 ms 50376 KB Output is correct
4 Correct 196 ms 50464 KB Output is correct
5 Correct 186 ms 50248 KB Output is correct
6 Correct 187 ms 50128 KB Output is correct
7 Incorrect 188 ms 50388 KB Unexpected end of file - int32 expected
8 Incorrect 193 ms 50492 KB Unexpected end of file - int32 expected
9 Correct 179 ms 49548 KB Output is correct
10 Correct 129 ms 39160 KB Output is correct
11 Correct 149 ms 41696 KB Output is correct
12 Correct 91 ms 31612 KB Output is correct
13 Correct 90 ms 31612 KB Output is correct
14 Incorrect 12 ms 23756 KB Unexpected end of file - int32 expected