QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#123234 | #5550. JOIRIS | lmeowdn | 15 | 1ms | 3704kb | C++14 | 2.4kb | 2023-07-11 21:35:43 | 2023-07-11 21:35:46 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=55;
int n,k,a[N],b[N],mx;
vp ans;
void clear() {
int mn=a[1];
rep(i,1,n) chmin(mn,a[i]);
rep(i,1,n) a[i]-=mn;
}
void oper(int x,int y) {
if(x==1) a[y]+=k;
else rep(j,y,y+k-1) a[j]++;
clear(); ans.eb(x,y);
}
signed main() {
n=read(), k=read();
rep(i,1,n) a[i]=read(), b[(i-1)%k]+=a[i];
rep(i,0,n%k-1) if(b[i]!=b[0]) return puts("-1"), 0;
rep(i,n%k,k-1) if(b[i]!=b[n%k]) return puts("-1"), 0;
clear();
rep(i,2,n) while(a[i]<a[i-1]) oper(1,i);
rep(i,k,n-1) while(a[i]!=a[i+1]) {
int x=i;
while(x>=k) oper(2,x-k+1), x-=k;
}
rep(i,1,k-1) {
for(int mx=0;;mx=0) {
rep(j,1,n) chmax(mx,a[j]);
if(a[i]>=mx) break;
oper(1,i);
}
}
int p=(n%k==0?k:n%k);
int mx=0; rep(i,p+1,k-1) chmax(mx,a[i]);
rep(i,1,n) {
int tm=(mx-a[i]+k-1)/k;
rep(j,1,tm) oper(1,i);
}
mx=0; rep(i,1,p) chmax(mx,a[i]);
rep(i,1,p) {
int tm=(mx-a[i]+k-1)/k;
rep(j,1,tm) oper(1,i);
}
for(int i=n%k+1;i<n;i+=k) {
rep(j,1,mx) oper(2,i);
}
rep(i,1,n) assert(a[i]==0);
printf("%d\n",(int)ans.size());
for(auto [x,y]:ans) printf("%d %d\n",x,y);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 15
Accepted
time: 1ms
memory: 3436kb
input:
34 2 2 5 41 47 8 27 42 17 43 47 47 12 49 33 41 18 4 16 15 28 9 13 25 44 20 40 25 16 2 20 0 41 6 16
output:
-1
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
26 2 32 42 0 0 20 22 4 19 13 37 22 30 50 17 23 1 11 7 22 3 26 25 45 32 38 38
output:
-1
result:
ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
32 2 3 42 8 32 34 44 2 4 19 40 49 47 25 6 46 7 40 22 38 6 32 45 4 35 16 29 47 6 1 22 0 14
output:
-1
result:
ok
Test #4:
score: -15
Wrong Answer
time: 1ms
memory: 3488kb
input:
28 2 9 21 26 30 0 46 33 7 36 29 28 0 33 21 29 37 15 44 33 14 14 34 32 4 49 23 48 19
output:
-1
result:
wrong answer
Subtask #2:
score: 15
Accepted
Test #17:
score: 15
Accepted
time: 1ms
memory: 3652kb
input:
3 2 38 27 0
output:
29 1 2 1 2 1 2 1 2 1 2 1 2 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 2 1 1 1 2 2
result:
ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
27 2 31 48 37 30 48 31 7 0 43 22 34 18 7 34 15 29 35 22 28 27 38 15 29 30 35 8 15
output:
533 1 3 1 3 1 3 1 3 1 3 1 3 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 5 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 ...
result:
ok
Test #19:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
19 2 26 12 20 18 44 46 2 28 17 47 3 35 0 42 43 40 4 45 42
output:
237 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 3 1 3 1 3 1 4 1 4 1 4 1 4 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1...
result:
ok
Test #20:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
29 2 40 19 38 29 10 48 4 3 30 42 29 21 28 27 43 2 7 24 27 39 0 13 21 35 48 15 7 33 34
output:
541 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 3 1 3 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 ...
result:
ok
Test #21:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
31 2 2 12 34 40 35 39 47 46 5 9 17 18 24 38 41 48 44 0 30 13 2 20 16 47 12 41 24 31 31 43 6
output:
538 1 5 1 5 1 5 1 6 1 8 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 12 1 1...
result:
ok
Test #22:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
5 2 29 14 34 0 14
output:
42 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 2 1 2 1 2 1 2 1 1 1 2 2 2 4
result:
ok
Test #23:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
7 2 18 38 0 7 7 45 43
output:
82 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 7 2 2 2 4 2 2 2 4 2 2 2 4 2 2 2 4 2 2 2 4 2 2 2 4 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
ok
Test #24:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
19 2 21 6 30 23 38 46 10 37 3 39 35 13 0 6 44 41 45 22 14
output:
248 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 4 1 4 1 4 1 4 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 8 1 8 1 8 1 8 1 8 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 10 1 10 1 10 1 10 1 11 1 11 1 11 1 11 1 11 1 11 1 12 1 12 1 12 1 1...
result:
ok
Test #25:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
19 2 47 30 36 24 22 25 5 9 20 7 19 8 44 11 45 24 22 0 48
output:
290 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 3 1 3 1 3 1 3 1 3 1 3 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 ...
result:
ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
19 2 8 11 10 27 23 26 9 36 3 2 46 0 47 46 26 29 19 5 0
output:
298 1 3 1 5 1 5 1 6 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 12 1 12 1 12 1 12 1 12 1 12 1 12 1 12 1 12 1 12 1 12 1 12 1 12 1 12 1 12 1 12 1 ...
result:
ok
Test #27:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
3 2 0 1 2
output:
3 2 1 1 1 2 2
result:
ok
Test #28:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
3 2 0 2 1
output:
3 1 3 2 1 1 1
result:
ok
Test #29:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
49 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
output:
1164 1 3 1 4 1 5 1 5 1 6 1 6 1 7 1 7 1 7 1 8 1 8 1 8 1 9 1 9 1 9 1 9 1 10 1 10 1 10 1 10 1 11 1 11 1 11 1 11 1 11 1 12 1 12 1 12 1 12 1 12 1 13 1 13 1 13 1 13 1 13 1 13 1 14 1 14 1 14 1 14 1 14 1 14 1 15 1 15 1 15 1 15 1 15 1 15 1 15 1 16 1 16 1 16 1 16 1 16 1 16 1 16 1 17 1 17 1 17 1 17 1 17 1 17 1...
result:
ok
Test #30:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
49 2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
output:
1188 1 2 1 3 1 4 1 4 1 5 1 5 1 6 1 6 1 6 1 7 1 7 1 7 1 8 1 8 1 8 1 8 1 9 1 9 1 9 1 9 1 10 1 10 1 10 1 10 1 10 1 11 1 11 1 11 1 11 1 11 1 12 1 12 1 12 1 12 1 12 1 12 1 13 1 13 1 13 1 13 1 13 1 13 1 14 1 14 1 14 1 14 1 14 1 14 1 14 1 15 1 15 1 15 1 15 1 15 1 15 1 15 1 16 1 16 1 16 1 16 1 16 1 16 1 16 ...
result:
ok
Test #31:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
49 2 0 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
output:
25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok
Test #32:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
49 2 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 0 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
output:
25 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27 1 27
result:
ok
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%