Codeforces Round ＃768 (Div. 1)（A-C)

Problem - 1630A - Codeforces

a

AC Code ：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <cctype>
#include <map>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <numeric>
#include <iomanip>
#include <functional>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
void solve() {
	int n, k;
	cin >> n >> k;
	if (k == 0) {
		for (int i = 0; i < n / 2; i++) {
			cout << i << " " << n - i - 1 << endl;
		}
	}
	else if (k < n - 1) {
		cout << k << " " << n - 1 << endl;
		cout << n - 1 - k << " " << 0 << endl;
		for (int i = 1; i < n / 2; i++) {
			if (i != k && i != n - k - 1) {
				cout << i << " " << n - i - 1 << endl;
			}
		}
	}
	else if (n == 4) {
		cout << -1 << endl;
	}
	else {
		cout << n - 2 << " " << n - 1 << endl;
		cout << 1 << " " << 3 << endl;
		cout << n - 4 << " " << 0 << endl;
		for (int i = 2; i < n / 2; i++) {
			if (i != 3) {
				cout << i << " " << n - i - 1 << endl;
			}
		}
	}
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

Problem - 1630B - Codeforces

b

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <cctype>
#include <map>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <numeric>
#include <iomanip>
#include <functional>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}
// Computational geometry 
// vector 
//struct Point {
//	double x, y;
//	Point operator - (Point a) {// Vector addition 
//		return { x - a.x,y - a.y };
//	}
//	Point operator + (Point a) {// Vector subtraction 
//		return { x + a.x,y + a.y };
//	}
//	double operator * (Point a) {// Point multiplication 
//		return x * a.x + y * a.y;
//	}
//	double operator % (Point a) {// Cross riding 
//		return x * a.y - y * a.x;
//	}
//	bool operator == (Point a) {// Whether the two points coincide 
//		return !sgn(x - a.x) && !sgn(y - a.y);
//	}
//	long double len() {// Returns the module of a vector 
//		return hypot(x, y);
//	}
//	Point rot(long double arg) {// Vector rotation 
//		long double Cos = cos(arg), Sin = sin(arg);
//		return { x * Cos - y * Sin,x * Sin + y * Cos };
//	}
//};
// A straight line  or  ray 
//struct Line {
//	Line() {}
//	Line (Point s,Point e): s(s),e(s){}
//	Point s, e;
//};

void solve() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int j = 0; j < n; j++) {
		cin >> a[j];
		a[j]--;
	}
	vector<int> cnt(n, 0);
	for (int j = 0; j < n; j++) {
		cnt[a[j]]++;
	}
	int x = 0, y = n;
	int R = 0;
	int sum = 0;
	for (int L = 0; L < n; L++) {
		while (R < n && sum - (n - sum) < k) {
			sum += cnt[R];
			R++;
		}
		if (sum - (n - sum) >= k) {
			if (y - x > R - L) {
				x = L;
				y = R;
			}
		}
		sum -= cnt[L];
	}
	vector<int> S(n + 1, 0);
	for (int j = 0; j < n; j++) {
		S[j + 1] = S[j];
		if (x <= a[j] && a[j] < y) {
			S[j + 1]++;
		}
		else {
			S[j + 1]--;
		}
	}
	vector<int> p(k + 1, -1);
	for (int j = 0; j <= n; j++) {
		if (0 <= S[j] && S[j] <= k) {
			if (p[S[j]] == -1) {
				p[S[j]] = j;
			}
		}
	}
	p[k] = n;
	cout << x + 1 << ' ' << y << "\n";
	for (int j = 0; j < k; j++) {
		cout << p[j] + 1 << ' ' << p[j + 1] << "\n";
	}
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

Problem - 1630C - Codeforces

You can pass with ordinary arrays , use vector can't make a good living , It's weird

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}
int a[200010], pos[200010], dp[200010];
void solve() {
	int n;
	cin >> n;
	memset(dp, 0x3f, sizeof(dp));
	// vector<int> a(200010);
	// vector<int> pos(200010);
	// vector<int> dp(200010, 0x3f);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pos[a[i]] = i;
	}
	dp[0] = 0;
	int cur = pos[a[1]];
	for (int i = 1; i <= n; i++) {
		dp[i] = min(dp[i - 1] + 1, dp[i]);
		cur = max(cur, pos[a[i]]);
		dp[cur] = min(dp[i] + 1, dp[cur]);
	}
	cout << n - dp[n] << endl;
    return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	// cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/