Submission #861933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
861933	2023-10-17T07:52:20 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]--;
	}
	
}


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	1057 ms	6176 KB	Time limit exceeded
2	Execution timed out	1034 ms	6216 KB	Time limit exceeded
3	Execution timed out	1064 ms	6308 KB	Time limit exceeded
4	Execution timed out	1045 ms	6092 KB	Time limit exceeded
5	Execution timed out	1029 ms	5968 KB	Time limit exceeded
6	Execution timed out	1026 ms	6064 KB	Time limit exceeded

Subtask #2

0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1052 ms	6404 KB	Time limit exceeded
2	Execution timed out	1066 ms	6252 KB	Time limit exceeded
3	Execution timed out	1041 ms	6548 KB	Time limit exceeded
4	Execution timed out	1078 ms	6660 KB	Time limit exceeded
5	Execution timed out	1010 ms	6336 KB	Time limit exceeded
6	Execution timed out	1038 ms	6716 KB	Time limit exceeded
7	Execution timed out	1061 ms	6564 KB	Time limit exceeded
8	Execution timed out	1057 ms	6188 KB	Time limit exceeded
9	Execution timed out	1050 ms	5172 KB	Time limit exceeded
10	Execution timed out	1065 ms	2652 KB	Time limit exceeded
11	Execution timed out	1036 ms	3592 KB	Time limit exceeded
12	Runtime error	290 ms	262144 KB	Execution killed with signal 9
13	Runtime error	287 ms	262144 KB	Execution killed with signal 9
14	Execution timed out	1034 ms	1376 KB	Time limit exceeded