oj.uz

답안 #862060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862060 2023-10-17T13:11:13 Z iskhakkutbilim Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 1000 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define all(a) a.begin(), a.end()

int n, k;
vector<int> ans;
int st[31];
vector<int> First[31];
int del, idx;
void f(int x, int depth){
	if(x <= 0) return;
	int mn = 1;
	while(st[mn] <= 0 && 31 >= mn) mn++;
	if(mn > x){
		ans.push_back(x);
		st[x]--;
		del++;
	}else if(First[x].empty() or First[x].back() + del > ans.size() + 1){
		f(x-1, depth + 1);
		f(x-1, depth + 1);
		
	}else if(First[x].back() + del <= ans.size() + 1){
		ans.push_back(x);
		First[x].pop_back();
		st[x]--;
	}else assert(false);
	
}


main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for(int i = 0;i < n; i++){
		int x; cin >> x;
		st[x]++;
		First[x].push_back(i + 1);
	}
	for(int i = 1;i <= 30; i++){
		reverse(all(First[i]));
	}
	f(30, 1);
	while(ans.size() < n + k){
		vector<int> have = ans;
		vector<int> merge;
		ans.clear();
		for(int i = 0;i < have.size(); i++){
			if(have[i] > 1){
				f(have[i]-1, 1);
				f(have[i]-1, 1);
				for(int j = 0;j < i; j++) merge.push_back(have[j]);
				for(int x : ans) merge.push_back(x);
				for(int j = i + 1; j < have.size(); j++){
					merge.push_back(have[j]);
				}
				break;
			}
		}
		if(merge.empty()) assert(false);
		ans = merge;
	}
	for(auto x : ans) cout << x << ' ';
	return 0;
}

Compilation message

zalmoxis.cpp: In function 'void f(int, int)':
zalmoxis.cpp:21:53: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  }else if(First[x].empty() or First[x].back() + del > ans.size() + 1){
      |                               ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:25:33: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  }else if(First[x].back() + del <= ans.size() + 1){
      |           ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
zalmoxis.cpp: At global scope:
zalmoxis.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){
      | ^~~~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:47:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |  while(ans.size() < n + k){
      |        ~~~~~~~~~~~^~~~~~~
zalmoxis.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i = 0;i < have.size(); i++){
      |                 ~~^~~~~~~~~~~~~
zalmoxis.cpp:57:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int j = i + 1; j < have.size(); j++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1060 ms 6884 KB Time limit exceeded
2 Execution timed out 1022 ms 7240 KB Time limit exceeded
3 Execution timed out 1057 ms 7064 KB Time limit exceeded
4 Execution timed out 1083 ms 6768 KB Time limit exceeded
5 Execution timed out 1046 ms 6824 KB Time limit exceeded
6 Execution timed out 1074 ms 6900 KB Time limit exceeded

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1028 ms 7072 KB Time limit exceeded
2 Execution timed out 1039 ms 7016 KB Time limit exceeded
3 Execution timed out 1042 ms 7316 KB Time limit exceeded
4 Execution timed out 1099 ms 7540 KB Time limit exceeded
5 Execution timed out 1052 ms 6944 KB Time limit exceeded
6 Execution timed out 1068 ms 7352 KB Time limit exceeded
7 Execution timed out 1024 ms 7240 KB Time limit exceeded
8 Execution timed out 1066 ms 7000 KB Time limit exceeded
9 Execution timed out 1036 ms 5736 KB Time limit exceeded
10 Execution timed out 1008 ms 2904 KB Time limit exceeded
11 Execution timed out 1037 ms 3844 KB Time limit exceeded
12 Runtime error 243 ms 262148 KB Execution killed with signal 9
13 Runtime error 239 ms 262144 KB Execution killed with signal 9
14 Execution timed out 1032 ms 1220 KB Time limit exceeded