This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
int A[50];
vpii sol;
int main() {
int i;
int N,K;
scanf("%d %d",&N,&K);
for (i = 0; i < N; i++) scanf("%d",&A[i]);
assert(K == 2);
if ((N & 1) == 0) {
int s = 0;
for (i = 0; i < N; i++) s += A[i];
if (s & 1) {
printf("-1\n");
return 0;
}
while (1) {
for (i = 0; i < N; i++) {
if (A[i] >= 2) break;
}
if (i < N) {
int m = 99;
for (i = 0; i < N; i++) {
if (A[i] == 0) {
sol.pb(mp(1,i+1));
A[i] += 2;
}
m = min(m,A[i]);
}
for (i = 0; i < N; i++) A[i] -= m;
}
else break;
}
while (1) {
vi v;
for (i = 0; i < N; i++) {
if (A[i] > 0) v.pb(i);
}
if (v.empty()) break;
for (i = 1; i < v.size(); i++) {
if (((v[i]-v[i-1]) & 1) == 1) break;
}
if (i >= v.size()) {
int x = v[0]/2;
sol.pb(mp(1,2*x+1));
sol.pb(mp(1,2*x+2));
for (i = 0; i < N/2; i++) {
if (i != x) {
sol.pb(mp(2,2*i+1));
if (!A[2*i] && !A[2*i+1]) {
sol.pb(mp(2,2*i+1));
A[2*i] = A[2*i+1] = 1;
}
}
}
A[2*x] ^= 1,A[2*x+1] ^= 1;
for (i = 0; i < N; i++) {
if ((i != 2*x) && (i != 2*x+1)) {
if (!A[i]) sol.pb(mp(1,i+1));
}
}
for (i = 0; i < N; i++) {
if ((i != v[0]) && A[i]) sol.pb(mp(1,i+1));
}
}
else {
int l = v[i-1],r = v[i];
A[l]--,A[r]--;
for (i = 0; i < N; i++) {
if ((i >= l) && (i <= r)) {
if ((i < r) && ((i-l) & 1)) sol.pb(mp(2,i+1));
}
else sol.pb(mp(1,i+1));
}
for (i = l; i <= r; i += 2) sol.pb(mp(2,i+1));
}
}
}
else {
while (1) {
for (i = 0; i < N; i++) {
if (A[i] >= 2) break;
}
if (i < N) {
int m = 99;
for (i = 0; i < N; i++) {
if (A[i] == 0) {
sol.pb(mp(1,i+1));
A[i] += 2;
}
m = min(m,A[i]);
}
for (i = 0; i < N; i++) A[i] -= m;
}
else break;
}
while (1) {
for (i = 0; i < N-1; i += 2) {
if (A[i] != A[i+1]) break;
}
if (i >= N-1) {
for (i = 0; i < N-1; i += 2) {
if (A[i] == 0) sol.pb(mp(2,i+1));
}
if (A[N-1] == 0) {
sol.pb(mp(1,N));
for (i = 0; i < N-1; i += 2) sol.pb(mp(2,i+1));
}
break;
}
else {
if (A[i] == 1) {
for (i = 0; i < N; i++) {
if (A[i] == 0) sol.pb(mp(1,i+1));
A[i] ^= 1;
}
}
else {
int x = i;
for (i = 0; i < x; i += 2) {
sol.pb(mp(2,i+1));
if ((A[i] == 0) && (A[i+1] == 0)) {
sol.pb(mp(2,i+1));
A[i] = A[i+1] = 1;
}
}
for (i = x+1; i < N; i += 2) {
sol.pb(mp(2,i+1));
if ((A[i] == 0) && (A[i+1] == 0)) {
sol.pb(mp(2,i+1));
A[i] = A[i+1] = 1;
}
}
sol.pb(mp(1,x+1));
A[x] = 1;
}
}
}
}
printf("%d\n",sol.size());
for (i = 0; i < sol.size(); i++) printf("%d %d\n",sol[i].first,sol[i].second);
return 0;
}
Compilation message (stderr)
joiris.cpp: In function 'int main()':
joiris.cpp:48:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 1; i < v.size(); i++) {
~~^~~~~~~~~~
joiris.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i >= v.size()) {
~~^~~~~~~~~~~
joiris.cpp:149:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
printf("%d\n",sol.size());
~~~~~~~~~~^
joiris.cpp:150:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < sol.size(); i++) printf("%d %d\n",sol[i].first,sol[i].second);
~~^~~~~~~~~~~~
joiris.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&K);
~~~~~^~~~~~~~~~~~~~~
joiris.cpp:15:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < N; i++) scanf("%d",&A[i]);
~~~~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |