Codeforces Round 908 (Div. 2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;

void solve() {
	int n;
	string s;
	cin >> n >> s;
	cout << s.back() << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

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

typedef long long ll;

void solve() {
	int n, a[105];
	map<int, int> ma;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
		++ma[a[i]];
	}
	if (ma.size() < 2) {
		printf("-1\n");
		return;
	}
	int x = 0, y = 0;
	for (auto &[a, b] : ma) {
		if (b >= 2) {
			if (!x) x = a;
			else y = a;
		}
	}
	if (!y) {
		printf("-1\n");
		return;
	}
	for (int i = 0; i < n; ++i) {
		int res = 1;
		if (a[i] == x) {
			res = 2;
			x = 0;
		} else if (a[i] == y) {
			res = 3;
			y = 0;
		}
		printf("%d ", res);
	}
	printf("\n");
}

int main() {
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr); cout.tie(nullptr);
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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

typedef long long ll;

const int N = 2e5+5;

int t[N];
bool vis[N];

void solve() {
	int n, k, r;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &r);
		t[(i + 1) % n] = r > n ? -1 : (i + 1 - r + n) % n;
		vis[i] = false;
	}
	// for (int i = 0; i < n; ++i) {
	// 	printf("%d ", t[i]);
	// }
	// printf("\n");
	int cnt = 0, u = 0;
	while (true) {
		vis[u] = true;
		int &v = t[u];
		if (v == -1) break;
		if (vis[v]) {
			printf("Yes\n");
			return;
		}
		u = v;
		++cnt;
	}
	printf(cnt >= k ? "Yes\n" : "No\n");
}

int main() {
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr); cout.tie(nullptr);
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

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

typedef long long ll;

template<class T> struct BIT {
	int n;
	T *t;
	bool need_free = true;

	inline int lb(int x) {
		return x & (-x);
	}

	// 构造空树状数组
	BIT(int n) {
		this->n = n;
		t = new T[n + 1]();
	}

	// n:数据数量 a:数据源(下标1开始) inplace:利用传入的数组
	BIT(int n, T *a, bool inplace = false) {
		this->n = n;
		need_free = !inplace;
		t = inplace ? a : new T[n + 1]();
		for (int i = 1; i <= n; ++i) {
			if (!inplace) t[i] = a[i];
			for (int x = lb(i) >> 1; x; x >>= 1) {
				t[i] += t[i - x];
			}
		}
	}

	~BIT() {
		if (need_free) delete[] t;
	}

	// 单点修改 a[x] += k
	void set(int x, T k) {
		for (; x <= n; x += lb(x)) t[x] = max(t[x], k);
	}

	// 查询前缀和
	T prefix(int x) {
		T c = 0;
		for (; x; x -= lb(x)) c = max(c, t[x]);
		return c;
	}

};

const int N = 2e5+5;
int b[N], dp[N];
struct Node {
	int i, a, t;
} a[N];

void solve() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i) {
		a[i].i = i;
		scanf("%d", &a[i].a);
	}
	sort(a, a + n, [](Node a, Node b) -> bool {
		return a.a < b.a;
	});
	int p = 1;
	a[0].t = 1;
	for (int i = 1; i < n; ++i) {
		if (a[i].a != a[i - 1].a) a[i].t = ++p;
		else a[i].t = p;
	}
	sort(a, a + n, [](Node a, Node b) -> bool {
		return a.i < b.i;
	});
	BIT<int> bit(p + 3);
	int mx = 0;
	for (int i = 0; i < n; ++i) {
		int x = bit.prefix(a[i].t - 1) + 1;
		dp[i] = x;
		mx = max(x, mx);
		bit.set(a[i].t, x);
	}
	for (int i = 0; i < m; ++i) {
		scanf("%d", &b[i]);
	}
	sort(b, b + m, greater<int>());

	vector<int> poses;
	for (int i = 0; i < n; ++i) {
		if (dp[i] == mx) poses.push_back(i);
	}
	int i = 0, j = 0;
	for (int &pos : poses) {
		for (; i < pos; ++i) {
			printf("%d ", a[i].a);
		}
		for (; j < m && b[j] >= a[pos].a; ++j) {
			printf("%d ", b[j]);
		}
		printf("%d ", a[pos].a);
		++i;
	}
	for (; i < n; ++i) {
		printf("%d ", a[i].a);
	}
	for (; j < m; ++j) {
		printf("%d ", b[j]);
	}
	printf("\n");
}

int main() {
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr); cout.tie(nullptr);
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}