Submission #312315

#	Time	Username	Problem	Language	Result	Execution time	Memory
312315		limabeans	JOIRIS (JOI16_joiris)	C++17	100 / 100	1 ms	640 KiB

joiris

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n, k;
int a[maxn];
int b[maxn]; //sum(ith column) mod k

vector<pair<int,int>> ans;


void print() {
    for (int i=0; i<n; i++) {
	cout<<a[i];
    }
    cout<<endl;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

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

    for (int i=0; i<n%k; i++) {
	if (b[i] != b[0]) {
	    out(-1);
	}
    }

    for (int i=n%k; i<k; i++) {
	if (b[i] != b[n%k]) {
	    out(-1);
	}
    }



    // make a[i-1] <= a[i]
    for (int i=1; i<n; i++) {
	while (a[i-1]>a[i]) {
	    ans.push_back({1, i});
	    a[i] += k;
	}
    }


    
    for (int i=k-1; i<n-1; i++) {
	int dy = a[i+1]-a[i];
	int left = n;
	for (int y=0; y<dy; y++) {
	    for (int j=i-k+1; j>=0; j-=k) {
		left = min(left, j);
		ans.push_back({2, j});
	    }
	}
	for (int j=i; j>=left; j--) {
	    a[j] += dy;
	}
    }


    
    for (int i=0; i<k-1; i++) {
	while (a[i]<a[n-1]) {
	    ans.push_back({1, i});
	    a[i] += k;
	}
	//assert(a[i]==a[0]);
    }


    //print();


    int dy = a[0]-a[n-1];
    for (int y=0; y<dy; y++) {
	for (int i=n-1; i-k+1>=0; i-=k) {
	    if (a[n-1]==a[i-k+1]) {
		ans.push_back({2, i-k+1});
		//watch(i-k+1);
	    } else {
		break;
	    }
	}
    }


    //watch(dy);



    cout<<ans.size()<<"\n";
    for (auto p: ans) {
	cout<<p.first<<" "<<1+p.second<<"\n";
    }
    
    
    return 0;
}

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