oj.uz

Submission #276759

# Submission time Handle Problem Language Result Execution time Memory
276759 2020-08-20T16:17:12 Z limabeans JOIRIS (JOI16_joiris) C++17
0 / 100
 1 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl


const int VERT = 1;
const int HORZ = 2;


using ll = long long;

const ll mod = 1e9+7;
const int maxn = 55;



int n, k;
int a[maxn];


vector<pair<int,int>> moves;


void insert(int dir, int i) {
    moves.push_back({dir, i});
    if (dir==VERT) {
	a[i] += k;
    } else {
	assert(i+k-1<=n);
	for (int j=i; j<i+k; j++) {
	    a[j]++;
	}
    }
}

void relax() {
    int lo = 1e9;
    for (int i=1; i<=n; i++) {
	lo = min(lo, a[i]);
    }
    for (int i=1; i<=n; i++) {
	a[i] -= lo;
    }
}

bool finished() {
    for (int i=1; i<=n; i++) {
	if (a[i]>0) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>k;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }

    assert(k==2 && n%2==0); //subtask1


    while (!finished()) {
	int mx = 0;
	for (int i=1; i<=n; i++) {
	    mx = max(mx, a[i]);
	}
	if (mx > 1) {
	    for (int i=1; i<=n; i++) {
		if (a[i]==0) {
		    insert(VERT, i);
		}
	    }
	    relax();
	} else {
	    // all 0 sections need to be even
	    for (int i=1; i<=n; ) {
		if (a[i]==1) {
		    i++; continue;
		}
		int j=i;
		while (j<=n && a[j]==0) {
		    j++;
		}
		int len = j-i;
		if (len%2==1) {
		    out(-1);
		} else {
		    for (int x=i; x<j; x+=k) {
			insert(HORZ, x);
		    }
		}
		i=j;
	    }

	    break;
	}
    }


    const int LIMIT = 1e4;
    assert((int)moves.size() <= LIMIT);

    cout<<moves.size()<<"\n";
    for (auto p: moves) {
	cout<<p.first<<" "<<p.second<<"\n";
    }
    
    
    
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Incorrect 1 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Incorrect 1 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Incorrect 1 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -