oj.uz

Submission #65168

# Submission time Handle Problem Language Result Execution time Memory
65168 2018-08-06T23:04:14 Z reality JOIRIS (JOI16_joiris) C++17
100 / 100
 9 ms 1196 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
vector < ll > A;
int MX,n,k;
ll One;
vector < pii > answer;
void G(int sz) {
	while (A.size() <= sz)
		A.pb(0ll);
}
int add1(int index) {
	int ok = 0;
	answer.pb(mp(1,index));
	int lst = -1;
	for (int i = 0;i < A.size();++i)
		if (A[i] & (1ll << index))
			lst = i;
	for (int cs = 0,i = lst + 1;cs < k && i <= lst + k;++cs,++i) {
		G(i);
		A[i] |= 1ll << index;
		if (A[i] == One) {
			A.erase(A.begin() + i);
			ok = 1;
			--i;--lst;
		}
	}
	return ok;
}
int add2(int index) {
	int ok = 0;
	answer.pb(mp(2,index));
	int lst = -1;
	for (int i = index;i < index + k;++i)
		for (int j = 0;j < A.size() && (A[j] & (1ll << i));++j)
				smax(lst,j);
	G(++lst);
	for (int i = index;i < index + k;++i)
		A[lst] |= 1ll << i;
	if (A[lst] == One)
		A.erase(A.begin() + lst),ok = 1;
	return ok;
}
int main(void) {
    cin>>n>>k;
    One = (1ll << n) - 1;
    vi s(n);
    for (auto & it : s)
    	cin>>it;
    vi sum(k,0);
    for (int i = 0;i < n;++i)
    	(sum[i % k] += s[i]) %= k;
    int ok = 0;
    for (int i = 0;i + 1 < (n % k);++i)
    	if (sum[i] != sum[i + 1])
    		return puts("-1") * 0;
    for (int i = (n % k);i + 1 < k;++i)
    	if (sum[i] != sum[i + 1])
    		return puts("-1") * 0;
    for (int i = 0;i < n;++i) {
    	G(s[i]);
    	for (int j = 0;j < s[i];++j)
    		A[j] |= 1ll << i;
    }
    for (int i = 1;i < n;++i) {
    	while (s[i - 1] > s[i]) {
    		add1(i);
    		s[i] += k;
    	}
    }
    for (int i = 0;i < A.size();++i) {
    	int w = -1;
    	while (w + 1 < n && !(A[i] & (1ll << (w + 1))))
    		++w;
    	while (w >= k - 1) {
    		if (add2(w - k + 1))
    			--i;
    		w -= k;
    	}
    }
    for (int i = 0;i < k - 1;++i) {
        while (!A.empty() && !(A.back() & (1ll << i)))
            add1(i);
    }
    while (!A.empty() && (A[0] & (1ll << (n % k)))) {
    	for (int i = 0;i < n;++i)
    		if (!(A[k - 1] & (1ll << i)))
    			add1(i);
    }
    if (!A.empty())
	for (int i = 0;i < (n % k);++i)
		while (!(A.back() & (1ll << i)))
			add1(i);
	while (!A.empty()) {
		for (int i = (n % k);i < n;i += k)
			add2(i);
	}
	cout << (answer.size()) << '\n';
	for (auto it : answer)
		cout << it.fi << ' ' << (it.se + 1) << '\n';
    return 0;
}

Compilation message

joiris.cpp: In function 'void G(int)':
joiris.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (A.size() <= sz)
         ~~~~~~~~~^~~~~
joiris.cpp: In function 'int add1(int)':
joiris.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0;i < A.size();++i)
                 ~~^~~~~~~~~~
joiris.cpp: In function 'int add2(int)':
joiris.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0;j < A.size() && (A[j] & (1ll << i));++j)
                  ~~^~~~~~~~~~
joiris.cpp: In function 'int main()':
joiris.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i < A.size();++i) {
                    ~~^~~~~~~~~~
joiris.cpp:103:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (!A.empty())
     ^~
joiris.cpp:107:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  while (!A.empty()) {
  ^~~~~
joiris.cpp:66:9: warning: unused variable 'ok' [-Wunused-variable]
     int ok = 0;
         ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 444 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 2 ms 572 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 2 ms 652 KB Output is correct
12 Correct 2 ms 652 KB Output is correct
13 Correct 3 ms 652 KB Output is correct
14 Correct 3 ms 672 KB Output is correct
15 Correct 3 ms 672 KB Output is correct
16 Correct 2 ms 696 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 700 KB Output is correct
2 Correct 2 ms 704 KB Output is correct
3 Correct 2 ms 704 KB Output is correct
4 Correct 2 ms 704 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 3 ms 736 KB Output is correct
8 Correct 2 ms 736 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 2 ms 764 KB Output is correct
11 Correct 3 ms 772 KB Output is correct
12 Correct 3 ms 776 KB Output is correct
13 Correct 4 ms 776 KB Output is correct
14 Correct 2 ms 784 KB Output is correct
15 Correct 3 ms 784 KB Output is correct
16 Correct 3 ms 784 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 444 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 2 ms 572 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 2 ms 652 KB Output is correct
12 Correct 2 ms 652 KB Output is correct
13 Correct 3 ms 652 KB Output is correct
14 Correct 3 ms 672 KB Output is correct
15 Correct 3 ms 672 KB Output is correct
16 Correct 2 ms 696 KB Output is correct
17 Correct 3 ms 784 KB Output is correct
18 Correct 2 ms 784 KB Output is correct
19 Correct 2 ms 800 KB Output is correct
20 Correct 3 ms 800 KB Output is correct
21 Correct 3 ms 800 KB Output is correct
22 Correct 2 ms 816 KB Output is correct
23 Correct 4 ms 828 KB Output is correct
24 Correct 3 ms 832 KB Output is correct
25 Correct 5 ms 832 KB Output is correct
26 Correct 3 ms 832 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 2 ms 860 KB Output is correct
29 Correct 3 ms 868 KB Output is correct
30 Correct 2 ms 868 KB Output is correct
31 Correct 3 ms 868 KB Output is correct
32 Correct 2 ms 868 KB Output is correct
33 Correct 2 ms 868 KB Output is correct
34 Correct 2 ms 868 KB Output is correct
35 Correct 2 ms 868 KB Output is correct
36 Correct 2 ms 868 KB Output is correct
37 Correct 3 ms 900 KB Output is correct
38 Correct 3 ms 900 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 444 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 2 ms 572 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 2 ms 652 KB Output is correct
12 Correct 2 ms 652 KB Output is correct
13 Correct 3 ms 652 KB Output is correct
14 Correct 3 ms 672 KB Output is correct
15 Correct 3 ms 672 KB Output is correct
16 Correct 2 ms 696 KB Output is correct
17 Correct 2 ms 700 KB Output is correct
18 Correct 2 ms 704 KB Output is correct
19 Correct 2 ms 704 KB Output is correct
20 Correct 2 ms 704 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 2 ms 736 KB Output is correct
23 Correct 3 ms 736 KB Output is correct
24 Correct 2 ms 736 KB Output is correct
25 Correct 2 ms 764 KB Output is correct
26 Correct 2 ms 764 KB Output is correct
27 Correct 3 ms 772 KB Output is correct
28 Correct 3 ms 776 KB Output is correct
29 Correct 4 ms 776 KB Output is correct
30 Correct 2 ms 784 KB Output is correct
31 Correct 3 ms 784 KB Output is correct
32 Correct 3 ms 784 KB Output is correct
33 Correct 3 ms 784 KB Output is correct
34 Correct 2 ms 784 KB Output is correct
35 Correct 2 ms 800 KB Output is correct
36 Correct 3 ms 800 KB Output is correct
37 Correct 3 ms 800 KB Output is correct
38 Correct 2 ms 816 KB Output is correct
39 Correct 4 ms 828 KB Output is correct
40 Correct 3 ms 832 KB Output is correct
41 Correct 5 ms 832 KB Output is correct
42 Correct 3 ms 832 KB Output is correct
43 Correct 4 ms 860 KB Output is correct
44 Correct 2 ms 860 KB Output is correct
45 Correct 3 ms 868 KB Output is correct
46 Correct 2 ms 868 KB Output is correct
47 Correct 3 ms 868 KB Output is correct
48 Correct 2 ms 868 KB Output is correct
49 Correct 2 ms 868 KB Output is correct
50 Correct 2 ms 868 KB Output is correct
51 Correct 2 ms 868 KB Output is correct
52 Correct 2 ms 868 KB Output is correct
53 Correct 3 ms 900 KB Output is correct
54 Correct 3 ms 900 KB Output is correct
55 Correct 3 ms 900 KB Output is correct
56 Correct 3 ms 900 KB Output is correct
57 Correct 2 ms 900 KB Output is correct
58 Correct 2 ms 912 KB Output is correct
59 Correct 2 ms 912 KB Output is correct
60 Correct 2 ms 912 KB Output is correct
61 Correct 2 ms 912 KB Output is correct
62 Correct 3 ms 912 KB Output is correct
63 Correct 2 ms 912 KB Output is correct
64 Correct 3 ms 1096 KB Output is correct
65 Correct 2 ms 1096 KB Output is correct
66 Correct 2 ms 1096 KB Output is correct
67 Correct 2 ms 1096 KB Output is correct
68 Correct 2 ms 1096 KB Output is correct
69 Correct 2 ms 1096 KB Output is correct
70 Correct 3 ms 1096 KB Output is correct
71 Correct 4 ms 1096 KB Output is correct
72 Correct 4 ms 1096 KB Output is correct
73 Correct 5 ms 1096 KB Output is correct
74 Correct 3 ms 1096 KB Output is correct
75 Correct 4 ms 1196 KB Output is correct
76 Correct 3 ms 1196 KB Output is correct
77 Correct 3 ms 1196 KB Output is correct
78 Correct 2 ms 1196 KB Output is correct
79 Correct 2 ms 1196 KB Output is correct
80 Correct 3 ms 1196 KB Output is correct
81 Correct 9 ms 1196 KB Output is correct
82 Correct 3 ms 1196 KB Output is correct
83 Correct 3 ms 1196 KB Output is correct
84 Correct 2 ms 1196 KB Output is correct
85 Correct 3 ms 1196 KB Output is correct
86 Correct 2 ms 1196 KB Output is correct
87 Correct 3 ms 1196 KB Output is correct
88 Correct 2 ms 1196 KB Output is correct
89 Correct 3 ms 1196 KB Output is correct
90 Correct 3 ms 1196 KB Output is correct
91 Correct 3 ms 1196 KB Output is correct
92 Correct 2 ms 1196 KB Output is correct