Submission #1254182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254182		trandangquang	JOIRIS (JOI16_joiris)	C++20	100 / 100	1 ms	328 KiB

joiris

/// just for comfirming 
#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=50+10;
int n,k,a[MAXN],b[MAXN],pre[MAXN],bs=-1;
int check(int g) {
	ffor(i,1,n) b[i]=((g-a[i])%k+k)%k;
	memset(pre,0,sizeof(pre));
	ffor(i,1,n-k+1) {
		pre[i]+=pre[i-1];
		b[i]=((b[i]-pre[i])%k+k)%k;
		pre[i+1]+=b[i],pre[i+k]-=b[i];
	}
	ffor(i,n-k+2,n) {
		pre[i]+=pre[i-1];
		if((b[i]-pre[i])%k!=0) return 0;	
	}
	return 1;
}
vector<pair<int,int>> ans;
void clear(void) {
	int mn=*min_element(a+1,a+n+1);
	ffor(i,1,n) a[i]-=mn;
	if(*max_element(a+1,a+n+1)>=k) {
		int mx=*max_element(a+1,a+n+1);	
		ffor(i,1,n) while(mx-a[i]>=k) a[i]+=k,ans.push_back({1,i});
	}
	mn=*min_element(a+1,a+n+1);
	ffor(i,1,n) a[i]-=mn;
	return ;
}
int main() {
//	freopen("tetris.in","r",stdin);
//	freopen("tetris.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	ffor(i,1,n) cin>>a[i];
	ffor(i,0,k-1) if(check(i)) {bs=i;break ;}
	if(bs==-1) return cout<<-1,0;
	int flg=0;
	ffor(i,1,n) b[i]=((bs-a[i])%k+k)%k;
	ffor(i,1,n-k+1) {
		int add=(b[i]%k+k)%k,mx=0;
		if(add) {
			ffor(j,i,i+k-1) mx=max(mx,a[j]);
			mx+=add;
			ffor(j,1,add) ans.push_back({2,i});
			ffor(j,1,n) if(!(i<=j&&j<=i+k-1)) {
				while(a[j]<mx) ans.push_back({1,j}),a[j]+=k;
				a[j]-=add;
			}
			ffor(j,i,i+k-1) b[j]=(b[j]-add)%k;
			flg=1,clear();
		}
	}
	if(!flg) ans.push_back({1,1}),a[1]+=k;
	int mx=*max_element(a+1,a+n+1);
	ffor(i,1,n) while(a[i]<mx) a[i]+=k,ans.push_back({1,i});
	cout<<ans.size()<<'\n';
	for(auto pr:ans) cout<<pr.first<<' '<<pr.second<<'\n';
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55