Submission #170716

#	Time	Username	Problem	Language	Result	Execution time	Memory
170716		dndhk	Zalmoxis (BOI18_zalmoxis)	C++14	10 / 100	390 ms	78060 KiB

zalmoxis

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 1;

int N, K;
vector<int> v;

vector<int> arr[40];

struct S{
	int idx;
	int num;
	int l, r;
};
vector<S> vt;
vector<S> ans;
deque<int> dq;
vector<int> answer;

int main(){
	scanf("%d%d", &N, &K);
	for(int i=0; i<N; i++){
		int x; scanf("%d", &x);
		v.pb(x);
	}
	for(int i=0; i<N; i++){
		vt.pb({i, v[i], i-1, (i==N-1)?-1:i+1});
		ans.pb({i, v[i], i-1, (i==N-1)?-1:i+1});
		arr[v[i]].pb(i);
	}
	for(int i=0; i<30; i++){
		for(int j=0; j<arr[i].size(); j++){
			if(vt[arr[i][j]].num==-1)	continue;
			int now = arr[i][j];
			while(vt[now].l!=-1 && vt[vt[now].l].num==i){
				now = vt[now].l;
			}
			while(1){
				if(vt[now].r!=-1 && vt[vt[now].r].num==i){
					vt.pb({vt[vt[now].r].idx, i+1, vt[now].l, vt[vt[now].r].r});
					if(vt[now].l!=-1){
						vt[vt[now].l].r = vt.size()-1;
					}if(vt[vt[now].r].r!=-1){
						vt[vt[vt[now].r].r].l = vt.size()-1;
					}
					vt[now].num = vt[vt[now].r].num = -1;
					arr[i+1].pb(vt.size()-1);
					now = vt[now].r;
					if(vt[now].r==-1 || vt[vt[now].r].num!=i){
						break;
					}
					now = vt[now].r;
				}else{
					K--;
					int l = vt[now].idx, r = ans[l].r; 
					ans.pb({0, i, l, r});
					ans[l].r = ans.size()-1; 
					if(r!=-1) ans[r].l = ans.size()-1;
					vt[now].num++;
					vt[now].idx = ans.size()-1;
					break;
				}
			}
		}
	}
	int t = 0;
	while(t!=-1){
		dq.pb(ans[t].num);
		t = ans[t].r;
	}
	int idx = 0;
	while(!dq.empty()){
		if(idx<v.size() && v[idx]==dq.front()){
			answer.pb(dq.front()); dq.pop_front();
			idx++;
		}else{
			if(K>0 && dq.front()>0){
				K--;
				int t = dq.front(); dq.pop_front();
				dq.push_front(t-1); dq.push_front(t-1);
			}else{
				answer.pb(dq.front()); dq.pop_front();
			}
		}
	}
	for(int i=0; i<answer.size(); i++){
		printf("%d ", answer[i]);
	}
	return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:54:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<arr[i].size(); j++){
                ~^~~~~~~~~~~~~~
zalmoxis.cpp:95:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(idx<v.size() && v[idx]==dq.front()){
      ~~~^~~~~~~~~
zalmoxis.cpp:108:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<answer.size(); i++){
               ~^~~~~~~~~~~~~~
zalmoxis.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:45:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
          ~~~~~^~~~~~~~~~

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