Submission #343194

#	Time	Username	Problem	Language	Result	Execution time	Memory
343194		S2speed	JOIRIS (JOI16_joiris)	C++17	15 / 100	1091 ms	2664 KiB

joiris

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

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define gcd __gcd 
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
struct piii {
	int first , second , third;
};

const ll MAX_N = 2e5 + 20 , md = 1e9 + 7;
 
ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n;
		}
		n *= n;
		k /= 2;
	}
	return res;
}

bool s2[MAX_N];
int a[MAX_N];
vector<pii> v;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int n , k , m = 0 , q = 0;
	cin>>n>>k;
	if(k != 2){
		return 0;
	}
	for(int i = 0 ; i < n ; i++){
		cin>>a[i];
		q += a[i];
		m = max(m , a[i]);
	}
	if(n % 2 == 0 && q % 2 == 1){
		cout<<"-1\n";
		return 0;
	}
	for(int i = 0 ; i < n ; i++){
		while(a[i] < m - 1){
			a[i] += 2;
			v.push_back({1 , i});
		}
		a[i] = (a[i] == m);
	}
	while(true){
		memset(s2 , 0 , sizeof(s2));
		vector<int> o , c;
		for(int i = 0 ; i < n ; i++){
			if(a[i]) o.push_back(i);
		}
		if(o.empty()) break;
		int os = o.size() , s = -1;
		for(int i = 1 ; i < os ; i++){
			if((o[i] - o[i - 1]) % 2 == 0){
				s = o[i];
				break;
			}
		}
		if(s == -1){
			for(int i = 0 ; i < os - 1 ; i++){
				for(int j = o[i] + 1 ; j < o[i + 1] ; j += 2){
					v.push_back({2 , j});
					a[j]++; a[j + 1]++;
				}
			}
			for(int j = o[0] - 1 ; j > 0 ; j -= 2){
				v.push_back({2 , j - 1});
				a[j]++; a[j - 1]++;
			}
			for(int j = o[os - 1] + 1 ; j < n - 1 ; j++){
				v.push_back({2 , j});
				a[j]++; a[j + 1]++;
			}
			o.clear();
			if(a[0] == 0){
				v.push_back({1 , 0});
			}
			if(a[n - 1] == 0){
				v.push_back({1 , n - 1});
			}
			for(int i = 0 ; i < n ; i++){
				a[i] = 1 - a[i];
			}
		} else {
			for(int i = 0 ; i < n - 1 ; i++){
				if(s2[i]) continue;
				if(i + 1 == s){
					v.push_back({1 , i});
					s2[i] = true;
					a[i]++;
					continue;
				}
				if(a[i] == 1 || a[i + 1] == 1){
					v.push_back({2 , i});
					s2[i] = true;
					s2[i + 1] = true;
					continue;
				}
				v.push_back({2 , i}); v.push_back({2 , i});
				s2[i] = true;
				s2[i + 1] = true;
				a[i] = 1;
				a[i + 1] = 1;
			}
			if(!s2[n - 1]){
				v.push_back({1 , n - 1});
				a[n - 1]++;
			}
			for(int i = 0 ; i < n ; i++){
				if(a[i] == 0){
					v.push_back({1 , i});
				}
				a[i] %= 2;
				a[i] = 1 - a[i];
			}
		}
	}
	cout<<v.size()<<'\n';
	for(auto p : v){
		cout<<p.first<<' '<<p.second + 1<<'\n';
	}
	return 0;
}

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