oj.uz

Submission #862071

# Submission time Handle Problem Language Result Execution time Memory
862071 2023-10-17T13:29:51 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[35];
vector<int> First[35];
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]));
	}
	/*
	5 1
	28 25 25 26 27
	
	6 1
	28 25 25 26 27 29
	
	5 1
	28  25 26 27 29
	*/
	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(int i = 0;i < ans.size(); i++) cout << ans[i] << ' ';
	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:24: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]
   24 |  }else if(First[x].back() + del <= ans.size() + 1){
      |           ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
zalmoxis.cpp: At global scope:
zalmoxis.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main(){
      | ^~~~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:56:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |  while(ans.size() < n + k){
      |        ~~~~~~~~~~~^~~~~~~
zalmoxis.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int i = 0;i < have.size(); i++){
      |                 ~~^~~~~~~~~~~~~
zalmoxis.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int j = i + 1; j < have.size(); j++){
      |                        ~~^~~~~~~~~~~~~
zalmoxis.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i = 0;i < ans.size(); i++) cout << ans[i] << ' ';
      |                ~~^~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1037 ms 4896 KB Time limit exceeded
2 Execution timed out 1059 ms 5104 KB Time limit exceeded
3 Execution timed out 1049 ms 5016 KB Time limit exceeded
4 Execution timed out 1071 ms 4816 KB Time limit exceeded
5 Execution timed out 1044 ms 4776 KB Time limit exceeded
6 Execution timed out 1035 ms 5028 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 5020 KB Time limit exceeded
2 Execution timed out 1058 ms 5104 KB Time limit exceeded
3 Execution timed out 1076 ms 5144 KB Time limit exceeded
4 Execution timed out 1063 ms 5288 KB Time limit exceeded
5 Execution timed out 1026 ms 4904 KB Time limit exceeded
6 Execution timed out 1098 ms 5436 KB Time limit exceeded
7 Execution timed out 1029 ms 5020 KB Time limit exceeded
8 Execution timed out 1063 ms 4888 KB Time limit exceeded
9 Execution timed out 1050 ms 4100 KB Time limit exceeded
10 Execution timed out 1048 ms 2140 KB Time limit exceeded
11 Execution timed out 1052 ms 2828 KB Time limit exceeded
12 Runtime error 273 ms 262144 KB Execution killed with signal 9
13 Runtime error 273 ms 262144 KB Execution killed with signal 9
14 Execution timed out 1046 ms 1200 KB Time limit exceeded