oj.uz

답안 #65735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65735 2018-08-08T15:31:43 Z Mamnoon_Siam Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 955 ms 86884 KB 
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
// #include <bits/extc++.h>
using namespace std;

#define debug(s) cout << #s << " = " << s << endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a, val) memset(a, val, sizeof (a))
#define PB push_back
#define endl '\n'
typedef long long ll;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}

template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
	return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;

template<typename T> using min_pq =
	std::priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

const int maxn = 2000005;

vector<int> v, nodes;
set<int> st;
int n, k, it = 0;

void dfs(int u, int lvl) {
	if(lvl == v[it]) {
		nodes.emplace_back(u);
		it++;
		return;
	}
	dfs(u << 1, lvl - 1);
	if(it == v.size() or lvl <= v[it]) {
		st.insert(u << 1 | 1);
		return;
	}
	dfs(u << 1 | 1, lvl - 1);
}

void print(int u, int lvl) {
	if(binary_search(nodes.begin(), nodes.end(), u)) {
		return void(cout << lvl << ' ');
	}
	print(u << 1, lvl - 1);
	print(u << 1 | 1, lvl - 1);
}

int32_t main () {
	// freopen("in", "r", stdin);
    cin >> n >> k;
    v.resize(n);
    for(int &b : v) cin >> b;
    dfs(1, 30);
	while(st.size() < k) {
		int top = *st.begin();
		st.erase(st.begin());
		st.insert(top << 1);
		st.insert(top << 1 | 1);
	}
	for(int b : st) {
		nodes.emplace_back(b);
	}
	sort(nodes.begin(), nodes.end());
	print(1, 30);
	cout << endl;
}

Compilation message

zalmoxis.cpp: In function 'int myrand(int, int)':
zalmoxis.cpp:18:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
zalmoxis.cpp:18:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
zalmoxis.cpp: In function 'void dfs(int, int)':
zalmoxis.cpp:47:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(it == v.size() or lvl <= v[it]) {
     ~~~^~~~~~~~~~~
zalmoxis.cpp: In function 'int32_t main()':
zalmoxis.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(st.size() < k) {
        ~~~~~~~~~~^~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 649 ms 12400 KB Output is correct
2 Correct 704 ms 14760 KB Output is correct
3 Correct 629 ms 16772 KB Output is correct
4 Correct 638 ms 18896 KB Output is correct
5 Correct 621 ms 20976 KB Output is correct
6 Correct 605 ms 22880 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 668 ms 25056 KB Output is correct
2 Correct 721 ms 27016 KB Output is correct
3 Correct 636 ms 29272 KB Output is correct
4 Correct 640 ms 31264 KB Output is correct
5 Correct 684 ms 33208 KB Output is correct
6 Correct 650 ms 35332 KB Output is correct
7 Correct 668 ms 37480 KB Output is correct
8 Correct 658 ms 39532 KB Output is correct
9 Correct 657 ms 49696 KB Output is correct
10 Correct 748 ms 72348 KB Output is correct
11 Correct 803 ms 72348 KB Output is correct
12 Correct 955 ms 86764 KB Output is correct
13 Correct 892 ms 86820 KB Output is correct
14 Correct 868 ms 86884 KB Output is correct