oj.uz

답안 #861934

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861934 2023-10-17T07:54:42 Z iskhakkutbilim Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 1000 ms 262144 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 1067 ms 4832 KB Time limit exceeded
2 Execution timed out 1039 ms 4936 KB Time limit exceeded
3 Execution timed out 1028 ms 5012 KB Time limit exceeded
4 Execution timed out 1042 ms 4816 KB Time limit exceeded
5 Execution timed out 1066 ms 5132 KB Time limit exceeded
6 Execution timed out 1047 ms 5016 KB Time limit exceeded

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1039 ms 5024 KB Time limit exceeded
2 Execution timed out 1024 ms 4964 KB Time limit exceeded
3 Execution timed out 1046 ms 5208 KB Time limit exceeded
4 Execution timed out 1039 ms 5284 KB Time limit exceeded
5 Execution timed out 1059 ms 4896 KB Time limit exceeded
6 Execution timed out 1036 ms 5436 KB Time limit exceeded
7 Execution timed out 1068 ms 5032 KB Time limit exceeded
8 Execution timed out 1033 ms 4888 KB Time limit exceeded
9 Execution timed out 1054 ms 3948 KB Time limit exceeded
10 Execution timed out 1060 ms 2140 KB Time limit exceeded
11 Execution timed out 1050 ms 3080 KB Time limit exceeded
12 Runtime error 271 ms 262144 KB Execution killed with signal 9
13 Runtime error 275 ms 262144 KB Execution killed with signal 9
14 Execution timed out 1045 ms 1276 KB Time limit exceeded