oj.uz

Submission #491392

# Submission time Handle Problem Language Result Execution time Memory
491392 2021-12-01T23:26:55 Z Yazan_Alattar Zalmoxis (BOI18_zalmoxis) C++14
85 / 100
 210 ms 50440 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];

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 204 ms 50124 KB Output is correct
2 Correct 195 ms 50412 KB Output is correct
3 Correct 197 ms 50280 KB Output is correct
4 Correct 193 ms 50288 KB Output is correct
5 Correct 200 ms 50396 KB Output is correct
6 Correct 185 ms 49932 KB Output is correct

Subtask #2
55.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 50228 KB Output is correct
2 Correct 210 ms 49992 KB Output is correct
3 Correct 195 ms 50324 KB Output is correct
4 Correct 198 ms 50356 KB Output is correct
5 Correct 195 ms 50404 KB Output is correct
6 Correct 190 ms 50176 KB Output is correct
7 Incorrect 189 ms 50388 KB Unexpected end of file - int32 expected
8 Incorrect 189 ms 50440 KB Unexpected end of file - int32 expected
9 Correct 176 ms 49552 KB Output is correct
10 Correct 134 ms 39140 KB Output is correct
11 Correct 149 ms 41620 KB Output is correct
12 Correct 95 ms 31644 KB Output is correct
13 Correct 93 ms 31688 KB Output is correct
14 Incorrect 13 ms 23752 KB Unexpected end of file - int32 expected