Submission #288346

#	Time	Username	Problem	Language	Result	Execution time	Memory
288346		sjimed	JOIRIS (JOI16_joiris)	C++14	100 / 100	1 ms	512 KiB

joiris

#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;
const ll Mod = 1e9 + 7;

int n, k;
int a[111];
int cnt[111];
vector<pii> ans;

void qr(int tmp, int x) {
	if(tmp == 1) {
		a[x] += k;
	}
	else {
		for(int i=x; i<x+k; i++)
			a[i]++;
	}

	ans.eb(tmp, x+1);
}

int main() {
	fast;

	cin >> n >> k;

	for(int i=0; i<n; i++) {
		cin >> a[i];

		cnt[i%k] += a[i];
		cnt[i%k] %= k;
	}

	for(int i=0; i<n%k; i++) {
		if(cnt[0] != cnt[i]) {
			cout << "-1\n";
			return 0;
		}
	}

	for(int i=n%k; i<k; i++) {
		if(cnt[k-1] != cnt[i]) {
			cout << "-1\n";
			return 0;
		}
	}

	for(int i=0; i<n; i++) {
		while(a[i-1] > a[i]) {
			qr(1, i);
		}
	}

	for(int i=0; i<=a[n-1]; i++) {
		int l = 0;
		for(int j=0; j<n; j++) {
			if(a[j] >= i) {
				l = j-1;
				break;
			}
		}

		for(int j=l; j-k+1 >= 0; j-=k) {
			qr(2, j-k+1);
		}
	}

	for(int i=0; i<k-1; i++) {
		while(a[i] < a[n-1]) {
			qr(1, i);
		}
	}


	int mx = 0;
	for(int i = n % k; i<k-1; i++) {
		mx = max(mx, a[i]);
	}

	for(int i=n%k; i<n; i++) {
		while(a[i] < mx) {
			qr(1, i);
		}
	}


	mx = 0;
	for(int i=0; i<n%k; i++) {
		mx = max(mx, a[i]);
	}

	for(int i=0; i<n%k; i++) {
		while(a[i] < mx) {
			qr(1, i);
		}
	}

	while(a[0] != a[n-1]) {
		for(int j=n%k; j<n; j+=k) {
			qr(2, j);
		}
	}

	cout << ans.size() << "\n";

	for(auto i : ans) {
		cout << i.fi << " " << i.se << "\n";
	}
}

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