oj.uz

Submission #170718

# Submission time Handle Problem Language Result Execution time Memory
170718 2019-12-26T07:57:44 Z dndhk Zalmoxis (BOI18_zalmoxis) C++14
55 / 100
 377 ms 75776 KB 
#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!=i)	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

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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 75016 KB Output is correct
2 Correct 347 ms 75360 KB Output is correct
3 Correct 348 ms 75776 KB Output is correct
4 Correct 351 ms 75144 KB Output is correct
5 Correct 343 ms 75136 KB Output is correct
6 Correct 349 ms 75116 KB Output is correct

Subtask #2
25.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 75240 KB Output is correct
2 Correct 346 ms 74624 KB Output is correct
3 Incorrect 342 ms 75464 KB Expected EOF
4 Incorrect 353 ms 75008 KB not a zalsequence
5 Correct 342 ms 75656 KB Output is correct
6 Correct 377 ms 75040 KB Output is correct
7 Correct 351 ms 75008 KB Output is correct
8 Incorrect 348 ms 75752 KB not a zalsequence
9 Incorrect 336 ms 65772 KB not a zalsequence
10 Incorrect 227 ms 31960 KB not a zalsequence
11 Incorrect 256 ms 45976 KB not a zalsequence
12 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected
13 Incorrect 2 ms 256 KB Unexpected end of file - int32 expected
14 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected