This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// In the name of god
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define Sort(x) sort(all(x))
#define debug(x) cerr << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;
const ll N = 105, MsK = 2e4, inf = 1e18, mod = 1e9 + 7;
ll n, k, a[N], b[N];
bool mrk[1505][55], mrk2[1505][55];
vector <pll> vec;
bool f(ll i){
for(ll j = 0; j < n; j ++)if(!mrk2[i][j])return 0;
return 1;
}
void update(){
for(ll i = 0; i <= 1504; i ++){
for(ll j = 0; j < n; j ++)mrk2[i][j] = mrk[i][j];
}
ll I = 1504;
for(ll i = 1504; i >= 0; i --){
if(f(i))continue;
for(ll j = 0; j < n; j ++)mrk[I][j] = mrk2[i][j];
I --;
}
while(I >= 0){
for(ll j = 0; j < n; j ++)mrk[I][j] = 0;
I --;
}
}
bool f2(){
for(ll i = (n % k); i < k - 1; i ++)if(mrk[1504][i])return 1;
return 0;
}
bool f3(){
for(ll i = 0; i < (n % k); i ++)if(mrk[1504][i])return 1;
return 0;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(ll i = 0; i < n; i ++){
cin >> a[i];
b[i % k] = (b[i % k] + a[i]) % k;
if(i > 0){
while(a[i] < a[i - 1]){
vec.pb({1, i + 1});
a[i] += k;
}
}
}
ll z = ((n % k) - 1 + k) % k;
for(ll i = 1; i <= z; i ++){
if(b[i] != b[i - 1])return cout << -1 << endl, 0;
}
z = (n % k);
for(ll i = z + 1; i < k; i ++){
if(b[i] != b[i - 1])return cout << -1 << endl, 0;
}
for(ll i = n - 1; i >= 0; i --)a[i] -= a[0];
ll Y = 1504;
for(ll i = 1; i < n; i ++){
for(ll j = 0; j < a[i]; j ++)mrk[Y - j][i] = 1;
}
for(ll i = Y; i > Y - a[n - 1]; i --){
for(ll j = n - 1; j > k - 2; j --){
if(!mrk[i][j]){
vec.pb({2, j - k + 2});
for(ll h = j; h > j - k; h --)mrk[i][h] = 1;
j -= k - 1;
}
}
}
update();
while(mrk[Y][n - 1]){
a[n - 1] = 0;
ll y = Y;
while(mrk[y][n - 1]){
y --;
a[n - 1] ++;
}
for(ll i = 0; i < k - 1; i ++){
ll yy = Y + 1;
for(ll j = 0; j <= Y; j ++){
if(mrk[j][i]){
yy = j;
break;
}
}
while(yy > Y - a[n - 1] + 1){
vec.pb({1, i + 1});
for(ll h = yy - 1; h >= yy - k; h --)mrk[h][i] = 1;
yy -= k;
}
}
update();
}
while((n % k) < k - 1 && f2()){
ll mx = 0;
for(ll i = (n % k); i < k - 1; i ++){
ll y = Y;
ll x = 0;
while(mrk[y][i]){
x ++;
y --;
}
mx = max(mx, x);
}
for(ll i = 0; i < n; i ++){
ll x = 0;
ll y = Y;
while(mrk[y][i]){
x ++;
y --;
}
while(x < mx){
for(ll j = Y - x; j > Y - x - k; j --)mrk[j][i] = 1;
x += k;
vec.pb({1, i + 1});
}
}
update();
}
while((n % k) - 1 >= 0 && f3()){
ll mx = 0;
for(ll i = 0; i < (n % k); i ++){
ll y = Y;
ll x = 0;
while(mrk[y][i]){
x ++;
y --;
}
mx = max(mx, x);
}
for(ll i = 0; i < (n % k); i ++){
ll x = 0;
ll y = Y;
while(mrk[y][i]){
x ++;
y --;
}
while(x < mx){
for(ll j = Y - x; j > Y - x - k; j --)mrk[j][i] = 1;
x += k;
vec.pb({1, i + 1});
}
}
ll x = (n % k);
while(x < n){
for(ll j = Y; j > Y - mx; j --){
for(ll i = x; i < x + k; i ++)mrk[j][i] = 1;
vec.pb({2, x + 1});
}
x += k;
}
update();
}
cout << vec.size() << endl;
for(auto i : vec)cout << i.F << ' ' << i.S << endl;
}
# | 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... |