oj.uz

답안 #365437

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
365437 2021-02-11T16:53:50 Z dynam1c Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 350 ms 61716 KB 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// if you're reading this i hope to meet you in IOI 2021
// RECHECK CONSTRAINTS AFTER MAKING A REDUCTION

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, k;
	cin >> n >> k;
	vector<array<int, 3>> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i][0], arr[i][1] = i, arr[i][2] = i+1;
	auto oarr = arr;
	priority_queue<array<int, 2>> aug;
	for (int ii = 0; ii < 30; ii++) {
		vector<array<int, 3>> ar2;
		for (int i = 0; i < arr.size(); i++) {
			if (arr[i][0] == ii) {
				if (i < arr.size()-1 and arr[i+1][0] == ii)
					ar2.push_back({arr[i][0]+1, arr[i][1], arr[i+1][2]}), i++;
				else 
					ar2.push_back({arr[i][0]+1, arr[i][1], arr[i][2]}), aug.push({arr[i][0], arr[i][2]});
			} else ar2.push_back(arr[i]);
		}
		arr = ar2;
	}
	while (aug.size() < k) {
		auto [x, i] = aug.top(); aug.pop();
		aug.push({x-1, i});
		aug.push({x-1, i});
	}
	vector<vector<int>> g(n+1);
	vector<int> res;
	while (!aug.empty()) {
		auto [x, i] = aug.top(); aug.pop();
		g[i].push_back(x);
	}
	arr = oarr;
	for (int i = 0; i <= n; i++) {
		reverse(all(g[i]));
		for (int e : g[i]) res.push_back(e);
		if (i < n) res.push_back(arr[i][0]);
	}
	for (int e : res) cout << e << " ";
	cout << endl;
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:29:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (int i = 0; i < arr.size(); i++) {
      |                   ~~^~~~~~~~~~~~
zalmoxis.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if (i < arr.size()-1 and arr[i+1][0] == ii)
      |         ~~^~~~~~~~~~~~~~
zalmoxis.cpp:39:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |  while (aug.size() < k) {
      |         ~~~~~~~~~~~^~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 61716 KB Output is correct
2 Correct 285 ms 61216 KB Output is correct
3 Correct 283 ms 60824 KB Output is correct
4 Correct 303 ms 61084 KB Output is correct
5 Correct 284 ms 61000 KB Output is correct
6 Correct 266 ms 61048 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 284 ms 60568 KB Output is correct
2 Correct 268 ms 61320 KB Output is correct
3 Correct 285 ms 61048 KB Output is correct
4 Correct 284 ms 61228 KB Output is correct
5 Correct 289 ms 61020 KB Output is correct
6 Correct 282 ms 60712 KB Output is correct
7 Correct 285 ms 61140 KB Output is correct
8 Correct 318 ms 61640 KB Output is correct
9 Correct 287 ms 54024 KB Output is correct
10 Correct 344 ms 35756 KB Output is correct
11 Correct 330 ms 44128 KB Output is correct
12 Correct 335 ms 25296 KB Output is correct
13 Correct 329 ms 25296 KB Output is correct
14 Correct 350 ms 23120 KB Output is correct