oj.uz

Submission #862072

# Submission time Handle Problem Language Result Execution time Memory
862072 2023-10-17T13:30:04 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(){
	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:54:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |  while(ans.size() < n + k){
      |        ~~~~~~~~~~~^~~~~~~
zalmoxis.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i = 0;i < have.size(); i++){
      |                 ~~^~~~~~~~~~~~~
zalmoxis.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int j = i + 1; j < have.size(); j++){
      |                        ~~^~~~~~~~~~~~~
zalmoxis.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  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 1056 ms 4864 KB Time limit exceeded
2 Execution timed out 1040 ms 4932 KB Time limit exceeded
3 Execution timed out 1058 ms 4928 KB Time limit exceeded
4 Execution timed out 1062 ms 4964 KB Time limit exceeded
5 Execution timed out 1057 ms 4680 KB Time limit exceeded
6 Execution timed out 1055 ms 4884 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 5032 KB Time limit exceeded
2 Execution timed out 1059 ms 5068 KB Time limit exceeded
3 Execution timed out 1052 ms 5264 KB Time limit exceeded
4 Execution timed out 1061 ms 5432 KB Time limit exceeded
5 Execution timed out 1027 ms 5020 KB Time limit exceeded
6 Execution timed out 1041 ms 5360 KB Time limit exceeded
7 Execution timed out 1060 ms 5144 KB Time limit exceeded
8 Execution timed out 1037 ms 4808 KB Time limit exceeded
9 Execution timed out 1083 ms 3928 KB Time limit exceeded
10 Execution timed out 1057 ms 2132 KB Time limit exceeded
11 Execution timed out 1044 ms 2752 KB Time limit exceeded
12 Runtime error 272 ms 262144 KB Execution killed with signal 9
13 Runtime error 261 ms 262144 KB Execution killed with signal 9
14 Execution timed out 1006 ms 1296 KB Time limit exceeded