oj.uz

Submission #491395

# Submission time Handle Problem Language Result Execution time Memory
491395 2021-12-01T23:30:20 Z Yazan_Alattar Zalmoxis (BOI18_zalmoxis) C++14
75 / 100
 207 ms 73992 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 && j){
                cout << j - 1 << " ";
                --k;
                int cur = j - 1;
                while(k){
                    if(cur == 0) 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 73660 KB Output is correct
2 Correct 199 ms 73956 KB Output is correct
3 Correct 193 ms 73792 KB Output is correct
4 Correct 191 ms 73736 KB Output is correct
5 Correct 195 ms 73820 KB Output is correct
6 Correct 198 ms 73388 KB Output is correct

Subtask #2
45.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 73744 KB Output is correct
2 Correct 195 ms 73488 KB Output is correct
3 Correct 203 ms 73908 KB Output is correct
4 Correct 206 ms 73864 KB Output is correct
5 Correct 200 ms 73836 KB Output is correct
6 Correct 194 ms 73692 KB Output is correct
7 Incorrect 196 ms 73776 KB Unexpected end of file - int32 expected
8 Incorrect 207 ms 73992 KB Unexpected end of file - int32 expected
9 Correct 184 ms 72784 KB Output is correct
10 Correct 145 ms 59420 KB Output is correct
11 Correct 163 ms 63324 KB Output is correct
12 Incorrect 22 ms 47180 KB Unexpected end of file - int32 expected
13 Incorrect 22 ms 47180 KB Unexpected end of file - int32 expected
14 Incorrect 23 ms 47232 KB Unexpected end of file - int32 expected