oj.uz

Submission #64792

# Submission time Handle Problem Language Result Execution time Memory
64792 2018-08-05T16:28:06 Z Good Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 388 ms 32756 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];

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

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);
	
	dq.push_front (30);
	
	int p = 0;
	int id = 1;
	
	while(id <= n) {
        int v = dq.front();
		dq.pop_front();
		
		if (v == A[id])
            id ++;
            
        else if (v < A[id])
              E[id - 1].pb (v), p ++;
        
		else {
              v --;
              if (v < 0) continue;
              dq.push_front (v);
              dq.push_front (v);
        }
        
    }
	
	for (int i = 0; i < dq.size(); i ++)
        E[id - 1].pb (dq[i]);
	
	p += dq.size();
	k -= p;	
			
	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:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < dq.size(); i ++)
                  ~~^~~~~~~~~~~
zalmoxis.cpp:92:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          for (int j = 0; j < dq.size(); j ++)
                          ~~^~~~~~~~~~~
zalmoxis.cpp:95:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          for (int j = 0; j < vv.size(); j ++)
                          ~~^~~~~~~~~~~
zalmoxis.cpp:34: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:37: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 274 ms 29892 KB Output is correct
2 Correct 223 ms 29892 KB Output is correct
3 Correct 329 ms 29904 KB Output is correct
4 Correct 273 ms 29960 KB Output is correct
5 Correct 236 ms 29960 KB Output is correct
6 Correct 324 ms 29960 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 29960 KB Output is correct
2 Correct 274 ms 30052 KB Output is correct
3 Correct 234 ms 30052 KB Output is correct
4 Correct 235 ms 30052 KB Output is correct
5 Correct 272 ms 30192 KB Output is correct
6 Correct 313 ms 30336 KB Output is correct
7 Correct 293 ms 30336 KB Output is correct
8 Correct 388 ms 30336 KB Output is correct
9 Correct 354 ms 32756 KB Output is correct
10 Correct 248 ms 32756 KB Output is correct
11 Correct 292 ms 32756 KB Output is correct
12 Correct 165 ms 32756 KB Output is correct
13 Correct 142 ms 32756 KB Output is correct
14 Correct 147 ms 32756 KB Output is correct