oj.uz

Submission #343197

# Submission time Handle Problem Language Result Execution time Memory
343197 2021-01-03T13:55:23 Z S2speed JOIRIS (JOI16_joiris) C++17
30 / 100
 1 ms 620 KB 
#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 += 2){
				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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 620 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Incorrect 0 ms 364 KB Unexpected end of file - int32 expected
18 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 1 ms 620 KB Output is correct
22 Correct 1 ms 620 KB Output is correct
23 Correct 1 ms 492 KB Output is correct
24 Correct 1 ms 620 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 492 KB Output is correct
27 Correct 1 ms 492 KB Output is correct
28 Correct 1 ms 492 KB Output is correct
29 Correct 1 ms 492 KB Output is correct
30 Correct 1 ms 492 KB Output is correct
31 Correct 1 ms 492 KB Output is correct
32 Correct 1 ms 492 KB Output is correct
33 Incorrect 0 ms 364 KB Unexpected end of file - int32 expected
34 Halted 0 ms 0 KB -