oj.uz

Submission #491394

# Submission time Handle Problem Language Result Execution time Memory
491394 2021-12-01T23:29:10 Z Yazan_Alattar Zalmoxis (BOI18_zalmoxis) C++14
85 / 100
 223 ms 74048 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 = 2000001;
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){
                cout << j - 1 << " ";
                --k;
                int cur = j - 1;
                while(k){
                    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 192 ms 73676 KB Output is correct
2 Correct 218 ms 73844 KB Output is correct
3 Correct 197 ms 73772 KB Output is correct
4 Correct 194 ms 73836 KB Output is correct
5 Correct 218 ms 73840 KB Output is correct
6 Correct 205 ms 73412 KB Output is correct

Subtask #2
55.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 73716 KB Output is correct
2 Correct 189 ms 73400 KB Output is correct
3 Correct 199 ms 73872 KB Output is correct
4 Correct 223 ms 73876 KB Output is correct
5 Correct 200 ms 73772 KB Output is correct
6 Correct 196 ms 73640 KB Output is correct
7 Incorrect 214 ms 73848 KB Unexpected end of file - int32 expected
8 Incorrect 208 ms 74048 KB Unexpected end of file - int32 expected
9 Correct 188 ms 73116 KB Output is correct
10 Correct 150 ms 62708 KB Output is correct
11 Correct 159 ms 65160 KB Output is correct
12 Correct 110 ms 55184 KB Output is correct
13 Correct 108 ms 55104 KB Output is correct
14 Incorrect 22 ms 47180 KB Unexpected end of file - int32 expected