oj.uz

Submission #491393

# Submission time Handle Problem Language Result Execution time Memory
491393 2021-12-01T23:28:25 Z Yazan_Alattar Zalmoxis (BOI18_zalmoxis) C++14
85 / 100
 221 ms 74112 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 > 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 201 ms 73656 KB Output is correct
2 Correct 210 ms 73920 KB Output is correct
3 Correct 203 ms 73776 KB Output is correct
4 Correct 198 ms 73840 KB Output is correct
5 Correct 211 ms 73820 KB Output is correct
6 Correct 203 ms 73364 KB Output is correct

Subtask #2
55.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 73712 KB Output is correct
2 Correct 215 ms 73404 KB Output is correct
3 Correct 207 ms 73876 KB Output is correct
4 Correct 203 ms 73904 KB Output is correct
5 Correct 216 ms 73732 KB Output is correct
6 Correct 221 ms 73648 KB Output is correct
7 Incorrect 209 ms 74000 KB Unexpected end of file - int32 expected
8 Incorrect 201 ms 74112 KB Unexpected end of file - int32 expected
9 Correct 198 ms 73028 KB Output is correct
10 Correct 137 ms 62696 KB Output is correct
11 Correct 162 ms 65136 KB Output is correct
12 Correct 96 ms 55144 KB Output is correct
13 Correct 99 ms 55112 KB Output is correct
14 Incorrect 23 ms 47216 KB Unexpected end of file - int32 expected