Submission #827442

#	Time	Username	Problem	Language	Result	Execution time	Memory
827442		79brue	JOIRIS (JOI16_joiris)	C++17	15 / 100	1 ms	340 KiB

joiris

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
int arr[52];

vector<pair<int, int> > ans;

void clean(){
	int v = *min_element(arr+1, arr+n+1);
	for(int i=1; i<=n; i++) arr[i] -= v;
}

int modCnt[52];

int main(){
	scanf("%d %d", &n, &k);
	for(int i=1; i<=n; i++) scanf("%d", &arr[i]);

	for(int i=1; i<=n; i++) modCnt[i%k] += arr[i];
	for(int i=0; i<k; i++) modCnt[i] %= k;
	if((n%k && *max_element(modCnt, modCnt+n%k) != *min_element(modCnt, modCnt+n%k)) ||
		*max_element(modCnt+n%k, modCnt+k) != *min_element(modCnt+n%k, modCnt+k)){
		puts("-1");
		return 0;
	}

	for(int i=1; i<n; i++){
		while(arr[i] > arr[i+1]){
			ans.push_back(make_pair(1, i+1));
			arr[i+1] += k;
		}
	}

	for(int i=1; i<n; i++){
		int v = arr[i+1] - arr[i];
		for(int j=i-k+1; j>=1; j-=k){
			for(int d=0; d<v; d++) ans.push_back(make_pair(2, j));
			for(int x=j; x<=j+k-1; x++) arr[x] += v;
		}
		clean();
	}

	int V = *max_element(arr+1, arr+n+1) / k + 1;
	for(int i=1; i<=k; i++){
		arr[i] += V * k;
		for(int d=0; d<V; d++) ans.push_back(make_pair(1, i));
		clean();
		if(*max_element(arr+n%k+1, arr+n+1) == 0) break;
	}
	assert(*max_element(arr+n%k+1, arr+n+1) == 0);

	V = *max_element(arr+1, arr+k+1);
	for(int i=1; i<=n%k; i++){
		int v = (V - arr[i]) / k;
		for(int d=0; d<v; d++) ans.push_back(make_pair(1, i));
	}
	clean();

	for(int i=n%k+1; i<=n; i+=k){
		for(int d=0; d<V; d++) ans.push_back(make_pair(2, i));
	}

	printf("%d\n", (int)ans.size());
	for(auto p: ans) printf("%d %d\n", p.first, p.second);
}

Compilation message (stderr)

joiris.cpp: In function 'int main()':
joiris.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
joiris.cpp:21:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~

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