Solution
Tutorial is loading...
Code
t = int(input())
for tc in range(t):
n, k = map(int, input().split())
cards = list(map(int, input().split()))
ct = {}
ans = n
for c in cards:
if c in ct:
ct.update({c: ct[c] + 1})
else:
ct.update({c: 1})
if ct[c] >= k:
ans = k - 1
print(ans)
Solution
Tutorial is loading...
Code
t = int(input())
for tc in range(t):
n, m = map(int, input().split())
gr = []
for i in range(n):
gr.append(input())
ans = "YES"
if gr[0][0] != gr[n - 1][m - 1]:
impossible = True
for j in range(m - 1):
if gr[0][j] != gr[0][j + 1] or gr[n - 1][j] != gr[n - 1][j + 1]:
impossible = False
if impossible:
ans = "NO"
impossible = True
for i in range(n - 1):
if gr[i][0] != gr[i + 1][0] or gr[i][m - 1] != gr[i + 1][m - 1]:
impossible = False
if impossible:
ans = "NO"
print(ans)
Solution
Tutorial is loading...
Code
t = int(input())
for tc in range(t):
n = int(input())
a = list(map(int, input().split()))
maxsize = max(a)
a.sort()
mexsize = 1
for sz in a:
if sz == mexsize:
mexsize = mexsize + 1
if mexsize > maxsize:
print("Alice" if maxsize % 2 == 1 else "Bob")
else:
print("Alice" if mexsize % 2 == 1 else "Bob")
1965B - Missing Subsequence Sum
Solution
Tutorial is loading...
Code
t = int(input())
for tc in range(t):
n, k = map(int, input().split())
i = 0
while (1 << (i + 1)) <= k:
i = i + 1
ans = [k - (1 << i), k + 1, k + 1 + (1 << i)]
for j in range(20):
if j != i:
ans.append(1 << j);
print(len(ans))
print(*ans)
Solution
Tutorial is loading...
Code
t = int(input())
for tc in range(t):
n = int(input())
s = input()
mn = 0
mx = 0
cur = 0
for c in s:
if (cur % 2 == 0) == (c == '1'):
cur = cur + 1
else:
cur = cur - 1
mn = min(mn, cur)
mx = max(mx, cur)
print(mx - mn)
Solution
Tutorial is loading...
Code
def getSubarraySums(a):
cts = []
for i in range(len(a)):
sm = 0
for j in range(i, len(a)):
sm = sm + a[j]
cts.append(sm)
cts.sort()
return cts
def getOddOccurringElements(cts):
odds = []
for ct in cts:
if len(odds) > 0 and ct == odds[-1]:
odds.pop()
else:
odds.append(ct)
return odds
def getPalindrome(odds, n):
a = [0] * n
prev = 0
idx = (n - 1) // 2
for x in odds:
if idx == n - 1 - idx:
a[idx] = x
else:
a[idx] = (x - prev) // 2
a[n - 1 - idx] = (x - prev) // 2
prev = x
idx = idx - 1
return a
def getLargestExcluded(bigList, smallList):
while len(smallList) > 0 and bigList[-1] == smallList[-1]:
bigList.pop()
smallList.pop()
return bigList[-1]
t = int(input())
for tc in range(t):
n = int(input())
subarraySums = list(map(int, input().split()))
subarraySums.sort()
odds = getOddOccurringElements(subarraySums)
missingSum = -1
if len(odds) > (n + 1) // 2:
oddvals = []
evenvals = []
for x in odds:
if x % 2 == 1:
oddvals.append(x)
else:
evenvals.append(x)
if len(evenvals) > 0 and len(oddvals) > 0:
missingSum = evenvals[0] if len(evenvals) == 1 else oddvals[0]
else:
b = getPalindrome(odds, n + 2)
bSums = getSubarraySums(b)
y = bSums[-1]
x = getLargestExcluded(bSums, subarraySums)
missingSum = 2 * x - y
else:
b = getPalindrome(odds, n - 2)
bSums = getSubarraySums(b)
y = bSums[-1]
x = getLargestExcluded(subarraySums, bSums)
missingSum = 2 * x - y
odds.append(missingSum)
odds.sort()
odds = getOddOccurringElements(odds)
ans = getPalindrome(odds, n)
print(*ans)
Solution
Tutorial is loading...
Code
n, m, k = map(int, input().split())
a = []
for i in range(n):
a.append(list(map(int, input().split())))
ans = []
for x in range(n):
for y in range(m):
for z in range(1, n + 1):
if y % 2 == 1:
ans.append([x, y, z, a[x][y]])
else:
ans.append([x, y, z, a[min(x, n - z)][y]])
for z in range(n + 1, n + k + 1):
if y % 2 == 1:
ans.append([x, y, z, a[x][y]])
else:
ans.append([x, y, z, z - n])
for x in range(n, n + k):
for y in range(m):
for z in range(1, n + 1):
if y % 2 == 1:
ans.append([x, y, z, x - n + 1])
else:
ans.append([x, y, z, a[n - z][y]])
ans.append([x, y, n + 1, x - n + 1])
for y in range(m):
for z in range(n + 2, n + k + 1):
ans.append([n, y, z, z - n])
for x in range(n + 1, n + k):
for z in range(n + 2, n + k + 1):
ans.append([x, 0, z, max(x - n + 1, z - n)])
print(len(ans))
for cube in ans:
print(cube[0] + 1, cube[1] + 1, cube[2] + 1, cube[3])
Solution
Tutorial is loading...
Code
/**
* author: tourist
* created: 26.11.2023 09:36:38
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
const long long inf = (long long) 1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<long long> l(n), r(n);
for (int i = 0; i < n; i++) {
cin >> l[i] >> r[i];
}
int original_n = n;
for (int rot = 0; rot < 2; rot++) {
// make all left ends distinct
map<long long, vector<long long>> mp;
for (int i = 0; i < n; i++) {
mp[l[i]].push_back(r[i]);
}
vector<long long> new_l, new_r;
auto it = mp.begin();
multiset<long long> s;
long long T = -inf;
while (true) {
if (s.empty()) {
if (it == mp.end()) {
break;
}
T = it->first;
}
while (it != mp.end() && T == it->first) {
s.insert(it->second.begin(), it->second.end());
++it;
}
assert(!s.empty());
new_l.push_back(T);
new_r.push_back(*s.begin());
s.erase(s.begin());
T += 1;
while (!s.empty() && *s.begin() < T) {
s.erase(s.begin());
}
}
swap(l, new_l);
swap(r, new_r);
n = (int) l.size();
for (int i = 0; i < n; i++) {
l[i] *= -1;
r[i] *= -1;
swap(l[i], r[i]);
}
}
sort(l.begin(), l.end());
sort(r.begin(), r.end());
vector<long long> ans(original_n + 1);
long long lx = -inf, rx = -inf;
int pl = 0, pr = 0;
int k = 0;
while (pl < n || pr < n) {
long long wait = min(pl < n ? l[pl] - lx : inf, pr < n ? r[pr] - rx : inf);
ans[k] += wait;
lx += wait;
rx += wait;
while (pl < n && l[pl] == lx) {
k += 1;
lx += 1;
pl += 1;
}
while (pr < n && r[pr] == rx) {
ans[k] += 1;
k -= 1;
rx += 1;
pr += 1;
}
}
for (int i = n; i > 1; i--) {
ans[i - 1] += ans[i];
}
for (int i = 1; i <= original_n; i++) {
cout << ans[i] << '\n';
}
return 0;
}