Codeforces Global Round 19

A. Sorting Parts

Sign in problem

Ideas

n Number , Separately 1~(n-1) Length before and after the infix to sort , If a certain time is not in non descending order, output "YES", Otherwise output "NO"

It's because the length of the prefix is from 1 Start , So as long as there is a number in the original array, it is not in non descending order , Then the non descending order must not be satisfied in a subsequent sort
eg: 2 1 4 5 6
Sort , First of all, yes The length is 1 Pre suffix sort of , Still 2 1 4 5 6 Does not satisfy non descending

Code

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef int Bool;
typedef long long ll;
#define MS(a, b) memset(a, b, sizeof(a))
int compare(const void* a, const void* b);

ll s[N]; 
int main() {
    
	int T;
	scanf("%d", &T);
	while (T--) {
    
		int n = 0;
		MS(s, 0);
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
    
			scanf("%lld", &s[i]);
		}
		int flag = 0;
		for (int i = 1; i < n; i++) {
    
			if (s[i] < s[i - 1]) flag = 1;
		}
		if (flag) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
int compare(const void* a, const void* b) {
    
	ElementType * s1 = (ElementType*)a;
	ElementType * s2 = (ElementType*)b;
	if (*s1 > *s2) return 1;
	else
	if (*s1 == *s2) return 0;
	else return -1;
}

C. Andrew and Stones

Sign in problem … But I still don't understand

thinking road

n Rubble , Every pile a_i individual , Choose three numbers 1 ≤ i < j < k ≤ n, also j Must be greater than or equal to 2
take j Medium stone , Each direction i Let's play one. towards k Let's play one.
Ask if you can move all the stones to In the first pile and the last pile

Sub situation

1. n == 3 , If the middle is an odd number, it cannot
2. n For any , The middle is full of 1, Do not move stones , Output -1
3. Satisfied

So directly judge whether it is all 1 that will do ,
Then record the minimum number of steps as ,(s[i] + 1) / 2 And

Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<time.h>

typedef int Bool;
typedef long long ll;
typedef unsigned long long ull;

#define N 100000+5
#define MS(a, b) memset(a, b, sizeof(a))

/* Except for  n == 3  The number in the middle of time is odd , And arbitrary n All medians of are less than 2, Anything else is ok */
ll s[N], sum, ans;
int main() {
    
	int T, n;
	scanf("%d", &T);
	while (T--) {
    
		sum = 0;// Record the total number of steps  (s[i] + 1) / 2 
		ans = 0;// Judge whether it's all  1 
		MS(s, 0);
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%lld", &s[i]);
		for (int i = 1; i < n - 1; i++) {
    
			ans |= (s[i] > 1) ;
			sum += (s[i] + 1) / 2;
		}
		if (!ans || (n == 3 && s[1] % 2 == 1))	printf("-1\n");
		else printf("%lld\n", sum);
	}
	return 0;
}