Submission #861934

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
861934	2023-10-17T07:54:42 Z	iskhakkutbilim	Zalmoxis (BOI18_zalmoxis)	C++17	0 / 100	1000 ms	262144 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	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

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