oj.uz

Submission #278064

# Submission time Handle Problem Language Result Execution time Memory
278064 2020-08-21T09:30:49 Z test2 Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 1000 ms 106392 KB 
#include<bits/stdc++.h>

#define I inline void 

using namespace std ; 

using ll = long long ; 
using ld = long double ; 

const int N = 1e5 + 7 ; 

// How interesting!

int n , k ; 

int main(){
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; 
	//freopen("in.in", "r" , stdin) ;

	cin >> n >> k ; 

	multiset<int> mul ; 

	multiset< pair<int , int >  > v ; 

	for(int i = 1 ;i <= n ;i++){
		int x ; 
		cin >> x ; 
		mul.insert(x) ; 
		v.insert({x , i }) ; 
	}

	set<int> adds ;

	for(int i = 0 ;i < k ;i++){
		auto it = mul.begin() ;
		auto itt = it ; 
		itt++ ; 
		if(it == mul.end() || (*itt) != (*it) ){
			adds.insert(*it) ; 

			mul.erase(it) ; 
			mul.insert( (*it) + 1) ; 
		}
		else {
			mul.erase(it) ; 
			mul.erase(itt) ; 
			mul.insert((*it) + 1) ; 
			i-- ; 
		}
	}

	int j = 0 ; 
	int last = 0 ; 
	vector<pair< int  , int > > ans ; 

	int st = 0 ; 
	for(auto u : v){
		if(!j) j = u.second , st =u.second; 
		auto it = adds.begin() ; 

		while(adds.size() && (*it) < u.first ){
			adds.erase(it) ; 
			ans.push_back({j++ , (*it)}) ; 
			it = adds.begin() ; 
		}
		if( u.second < st )
			ans.push_back({ u.second , u.first}) ; 
		else 
			ans.push_back({j++  , u.first}) ;
	}

	for(auto u : adds)
		ans.push_back({j++ , u}) ; 

	sort(ans.begin(), ans.end()) ;
	for(auto u : ans)
		cout<< u.second <<" ";

	return 0 ; 
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:55:6: warning: unused variable 'last' [-Wunused-variable]
   55 |  int last = 0 ;
      |      ^~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 106392 KB Time limit exceeded
2 Execution timed out 1107 ms 104912 KB Time limit exceeded
3 Execution timed out 1104 ms 105096 KB Time limit exceeded
4 Execution timed out 1107 ms 104672 KB Time limit exceeded
5 Execution timed out 1097 ms 104692 KB Time limit exceeded
6 Execution timed out 1050 ms 104676 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 104652 KB Time limit exceeded
2 Execution timed out 1078 ms 105356 KB Time limit exceeded
3 Execution timed out 1101 ms 105556 KB Time limit exceeded
4 Execution timed out 1096 ms 105932 KB Time limit exceeded
5 Execution timed out 1096 ms 104808 KB Time limit exceeded
6 Execution timed out 1066 ms 104692 KB Time limit exceeded
7 Execution timed out 1080 ms 104712 KB Time limit exceeded
8 Execution timed out 1095 ms 104684 KB Time limit exceeded
9 Execution timed out 1092 ms 86120 KB Time limit exceeded
10 Incorrect 670 ms 61324 KB doesn't contain S as a subsequence
11 Incorrect 938 ms 60776 KB doesn't contain S as a subsequence
12 Incorrect 470 ms 62200 KB doesn't contain S as a subsequence
13 Incorrect 477 ms 62164 KB doesn't contain S as a subsequence
14 Incorrect 442 ms 62164 KB not a zalsequence