Submission #139020

#	Time	Username	Problem	Language	Result	Execution time	Memory
139020		math0_0	Zalmoxis (BOI18_zalmoxis)	C++11	30 / 100	569 ms	46176 KiB

zalmoxis

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;


int main(){
	ll n, k;
	cin >> n >> k;
	
	//all values between 1 and 30
	
	//for k = 1
	//smallest integer in input must have 2 consecutive of it, else insta solve
	//group and ascend?
	vector<pl> book[31];//book[i] stores pos of numbers i
	for(ll one = 0; one < 31; one++){
		book[one].push_back(make_pair(-2, -2));
		book[one].push_back(make_pair(n+1, n+1));
	}
	
	ll tp, insidx = -1, insval = -1;
	ll a[n];
	for(ll one = 0; one < n; one++){
		cin >> tp;
		book[tp].push_back(make_pair(one, one));
		a[one] = tp;
	}
	
	for(ll one = 0; one < 30; one++){
		ll nums = book[one].size()-2;
		sort(book[one].begin(), book[one].end());
		if(nums%2){
			insval = one;
			for(ll two = 1; two <= nums; two++){
				ll lb = book[one][two-1].second;
				ll cl = book[one][two].first;
				ll cr = book[one][two].second;
				ll rb = book[one][two+1].first;
				
				if(cl-lb!=1 && rb-cr!=1){insidx = cr; two = nums+2; one = 31;}
				else{book[one][two+1].second = -2; two++;}
			}
		}
		else{
			for(ll two = 1; two < nums; two+=2){
				book[one+1].push_back(make_pair(book[one][two].first, book[one][two+1].second));
			}
		}
	}
	
	for(ll one = 0; one < n; one++){
		cout << a[one] << ' ';
		if(one == insidx){cout << insval << ' ';}
	}
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:37:24: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
    for(ll two = 1; two <= nums; two++){
                    ~~~~^~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 0 / 70