Submission #862060

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
862060	2023-10-17T13:11:13 Z	iskhakkutbilim	Zalmoxis (BOI18_zalmoxis)	C++17	0 / 100	1000 ms	262148 KB

zalmoxis

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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