QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#123234#5550. JOIRISlmeowdn15 1ms3704kbC++142.4kb2023-07-11 21:35:432023-07-11 21:35:46

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 21:35:46]
  • 评测
  • 测评结果:15
  • 用时:1ms
  • 内存:3704kb
  • [2023-07-11 21:35:43]
  • 提交

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%