oj.uz

Submission #64797

# Submission time Handle Problem Language Result Execution time Memory
64797 2018-08-05T16:45:42 Z Good Zalmoxis (BOI18_zalmoxis) C++17
45 / 100
 277 ms 67708 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ff first
#define ss second
#define Maxn 1000003
#define ll long long
#define pb push_back
#define Inf 1000000009
#define ppb() pop_back()
#define pii pair <int , int>
#define mid(x, y) (x + y) / 2
#define all(x) x.begin(),x.end()
#define llInf 1000000000000000009
#define tr(i, c) for(__typeof(c).begin() i = (c).begin() ; i != (c).end() ; i++)
using namespace std;
using namespace __gnu_pbds;
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> order;

int n, k;
ll cnt[33];
int A[Maxn];
int P[Maxn];

deque <int> dq;
vector <int> E[Maxn], v1;

int main () {
	//freopen ("file.in", "r", stdin);
	//freopen ("file.out", "w", stdout);
	
 	//srand ((unsigned) time ( NULL ));
	//int randomNumber = rand() % 10 + 1;

	scanf ("%d%d", &n, &k);

	for (int i = 1; i <= n; i++) {
		scanf ("%d", A + i);
		
		int e = A[i];
		while (v1.size() > 0 and v1.back() == e)
			e ++, v1.ppb ();
		
		v1.pb (e);
		P[v1.size() - 1] = i;	
	}	
		
	int sm = 0;
			
	int mn = 40;	
	for (auto i: v1)
		mn = min (mn, i);		
	
	for (int i = mn; i < 30; i++) {
		vector <int> v2;
		
		for (int j = 0; j < v1.size(); j++) {
			if (i == v1[j])
				sm ++, v2.pb (i), E[P[j]].pb (i);
			
			int e = v1[j];
			while (v2.size() > 0 and e == v2.back())	
				e ++, v2.ppb();
				
			v2.pb (e);
			P[v2.size() - 1] = P[j];	
		}		
		v1 = v2;
	}
			
	assert (sm <= k);		
	k -= sm;	
			
	for (int i = 1; i <= n; i++) {
		printf ("%d ", A[i]);
		
		for (auto l: E[i]) {
			vector <int> vv;
        	dq.clear();
        	dq.push_back (l);
        	
			while(k > 0 && !dq.empty()){
            	int v = dq.front();
                dq.pop_front();
                v --;
                
                if (v >= 0) {
                      dq.push_front(v);
                      dq.push_front(v);
                      k --;
                } 
				else
                      vv.push_back(0);
          }
          
        	for (int j = 0; j < dq.size(); j ++)
                vv.push_back (dq[j]);
                
        	for (int j = 0; j < vv.size(); j ++)
                printf ("%d ", vv[j]);
					
		}	
	}	
	
	return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:57:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v1.size(); j++) {
                   ~~^~~~~~~~~~~
zalmoxis.cpp:96:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          for (int j = 0; j < dq.size(); j ++)
                          ~~^~~~~~~~~~~
zalmoxis.cpp:99:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          for (int j = 0; j < vv.size(); j ++)
                          ~~^~~~~~~~~~~
zalmoxis.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &k);
  ~~~~~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:38:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", A + i);
   ~~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 29816 KB Output is correct
2 Correct 245 ms 29868 KB Output is correct
3 Correct 277 ms 29992 KB Output is correct
4 Correct 249 ms 29992 KB Output is correct
5 Correct 226 ms 29992 KB Output is correct
6 Correct 233 ms 29992 KB Output is correct

Subtask #2
15.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 30044 KB not a zalsequence
2 Runtime error 168 ms 56156 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 176 ms 56424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 275 ms 58180 KB not a zalsequence
5 Incorrect 223 ms 58180 KB not a zalsequence
6 Incorrect 227 ms 58180 KB not a zalsequence
7 Incorrect 219 ms 58180 KB not a zalsequence
8 Incorrect 234 ms 58180 KB not a zalsequence
9 Runtime error 213 ms 66500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 210 ms 66500 KB not a zalsequence
11 Incorrect 265 ms 67708 KB not a zalsequence
12 Correct 125 ms 67708 KB Output is correct
13 Correct 122 ms 67708 KB Output is correct
14 Correct 146 ms 67708 KB Output is correct