Educational Codeforces Round 117 (Rated for Div. 2)【A - C】

Educational Codeforces Round 117 (Rated for Div. 2)【A - C】

被二分干碎了…

A Distance

观察规律，判断一下奇偶就行，如果 x + y x+y x+y 为奇数势必不能分一半出来，如果是偶数，则构造偶数坐标即可。

#include 
using namespace std;
#define endl 'n'
#define ll long long
void solve() {
	int x, y;
	cin >> x >> y;
	int z = x + y;
	if(z & 1) {
		cout << -1 << " " << -1 << endl;
	}
	else {
		if(x & 1) x++;
		if(y & 1) y--;
		cout << x / 2 <<" " << y / 2 << endl;
	}
	return ;
}
int main() {
	int t;
	cin >> t;
	while(t--)
		solve(); 
	return 0;
}

---

B. Special Permutation

贪心：左边尽可能放大的，右边尽可能放小的，如果最后答案数组的大小不够 n n n，输出 − 1 -1 −1 即可

时间复杂度： O ( n ) O(n) O(n)

#include 
using namespace std;
#define endl 'n'
#define ll long long
void solve() {
	int a, b, c;
	cin >> a >> b >> c;
	if(b > a or c > a) {
		cout << -1 << endl;
		return ;
	}
	map vis;
	vis.clear();
	vector ans;
	ans.clear();
	
	ans.push_back(b);
	vis[b] = 1;
	for(int i = a, cnt = 1; i >= b; i--) {
		if(i == c or vis[i]) continue;
		if(cnt == a / 2)
			break;
		ans.push_back(i);
		vis[i] = 1;
		cnt++;
	}
	if(vis[c]) {
		cout << -1 << endl;
		return ;
	}
	
	ans.push_back(c);
	vis[c] = 1;
	for(int i = 1, cnt = 1; i <= c; i++) {
		if(vis[i] or i == b)
			continue;
		if(cnt == a / 2) 
			break;
		
		ans.push_back(i);
		vis[i] = 1;
		cnt++;
	}
	
	if(ans.size() != a) {
		cout << -1 << endl;
		return ;
	}
	
	for(auto i : ans) {
		cout << i <<" ";
	}
	cout << endl;
	return ;
}
int main() {
	int t;
	cin >> t;
	while(t--)
		solve(); 
	return 0;
}

---

C. Chat Ban

首先 1 → k − 1 → k → k − 1 → 1 1 → k-1→k→k-1→1 1→k−1→k→k−1→1，可以推出两个等差数列的公式，之后套个二分进去做就好了,我用的 i n t 128 int128 int128 写的，肯定有好的做法，但是我想睡觉了…

#include 
using namespace std;
#define endl 'n'
#define int __int128
int k, s;
int sum2(int n) {
	int a = n * k;
	int b = (n * n + n)/ 2;
	return a - b;
}
int sum1(int n) {
	return n * (n + 1) / 2;
}
void read(__int128 &X) {
	X = 0;
	int w=0; char ch=0;
	while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
	while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
	if (w) X = -X;
	return ;
}
void print(__int128 x) {
	if(!x) return ;
	if(x < 0) {
		putchar('-');
		x = -1;
	}
	print(x / 10);
	putchar(x % 10 + '0');
	return ;
}
void solve() {
	read(k);
	read(s);
	if(s >= k * k) {
		print(2 * k - 1);
		puts("");
		return ;
	}
	else {
		int now = sum1(k);
		if(s < now) {
			int l = 1, r = k - 1;
			while(l < r) {
				int mid = l + r + 1 >> 1;
				int flag = sum1(mid);
				if(s == flag) {
					print(mid);
					puts("");
					return ;
				}
				if(flag < s)
					l = mid + 1;
				else 
					r = mid - 1;
			}
			while(sum1(r) < s) r++;
			print(r);
			puts("");
		}
		
		else if(s == now) { 
			print(k);
			puts("");
		}
		
		else {
			int l = k - 1, r = 1;
			while(l > r) {
				int mid = l + r + 1 >> 1;
				int flag = sum1(k) + sum2(mid);
				if(s == flag) {
					print(mid + k);
					puts("");
					return ;
				}
				if(flag < s) {
					r = mid + 1;
				}
				else {
					l = mid - 1;
				}
			}
			while(sum1(k) + sum2(l) < s) l++;
			print(l + k);
			puts("");
		}
	}
	return ;
}
signed main() {
	int t;
	read(t);
	while(t--)
		solve(); 
	return 0;
}