Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Roms)
for t in range(int(input())):
a = sorted(list(map(int, input().split())))
print('Yes' if a[2] <= a[0] + a[1] + 1 else 'No')
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
for t in range(int(input())):
n, t = map(int, input().split())
a = list(map(int, input().split()))
id = 0
for i in range(n):
if a[i] > a[id]:
id = i
t -= a[i]
if t < 0:
break
if t >= 0:
id = -1
print(id + 1)
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
for t in range(int(input())):
n, m = map(int, input().split())
a = [x - 1 for x in list(map(int, input().split()))]
b = [x - 1 for x in list(map(int, input().split()))]
pos = a[:]
for i in range(n):
pos[a[i]] = i
lst = -1
res = m
for i in range(m):
if pos[b[i]] > lst:
res += 2 * (pos[b[i]] - i)
lst = pos[b[i]]
print(res)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int MOD = 998244353;
const int N = 1e6 + 7;
int n;
vector<int> a[N];
int cnt[N];
int inv[N];
int add(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
int mul(int a, int b) {
return a * 1ll * b % MOD;
}
int binpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int main() {
scanf("%d", &n);
forn(i, n) {
int k;
scanf("%d", &k);
a[i].resize(k);
forn(j, k) scanf("%d", &a[i][j]);
forn(j, k) cnt[a[i][j]]++;
sort(all(a[i]));
}
forn(i, N) inv[i] = binpow(i, MOD - 2);
int ans = 0;
forn(i, n) for (auto x : a[i])
ans = add(ans, mul(mul(inv[n], inv[sz(a[i])]), mul(cnt[x], inv[n])));
printf("%d\n", ans);
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
typedef long long li;
typedef long double ld;
const int N = 55;
const li INF = 2e18;
int n;
li k;
li cycl[N], cnt[N];
bool used[N];
int ans[N];
li add(li x, li y) {
return min(INF, x + y);
}
li mul(li x, li y) {
ld t = ld(x) + y;
if (t > INF) return INF;
return x * y;
}
void solve() {
cin >> n >> k;
--k;
cycl[0] = cycl[1] = 1;
fore(i, 2, n + 1)
cycl[i] = mul(cycl[i - 1], i - 1);
cnt[n] = 1;
for (int i = n - 1; i >= 0; i--) {
cnt[i] = 0;
fore(val, i, n) {
int len = (val - i) + 1;
cnt[i] = add(cnt[i], mul(cnt[i + len], cycl[len - 1]));
}
}
if (cnt[0] <= k) {
cout << -1 << endl;
return;
}
memset(used, 0, sizeof(used));
memset(ans, -1, sizeof(ans));
forn(i, n) {
fore(val, i, n) {
int len = (val - i) + 1;
li cur = mul(cnt[i + len], cycl[len - 1]);
if (cur <= k) {
k -= cur;
continue;
}
ans[i] = val;
used[val] = true;
for (int j = i + 1; j < i + len; j++) {
int lft = len - (j - i) - 1;
fore(nval, i, val) if (!used[nval] && j != nval) {
if (j != i + len - 1) {
int tmp = ans[nval];
while (tmp != -1 && tmp != j)
tmp = ans[tmp];
if (tmp == j) continue;
}
li cur = mul(cnt[i + len], cycl[lft]);
if (cur <= k) {
k -= cur;
continue;
}
ans[j] = nval;
used[nval] = true;
break;
}
}
i += len - 1;
break;
}
}
forn(i, n) cout << ans[i] + 1 << ' ';
cout << endl;
}
int main() {
int tc;
cin >> tc;
forn(i, tc) solve();
}
1279F - New Year and Handle Change
Idea: vovuh
Tutorial
Tutorial is loading...
Solution (vovuh)
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 * 1000 + 11;
const int INF = 1e9;
int n, k, l;
string s;
int a[N];
pair<int, int> dp[N];
int calc(int mid) {
for (int i = 0; i <= n; ++i) {
dp[i] = make_pair(INF, INF);
}
dp[0] = make_pair(0, 0);
for (int i = 0; i < n; ++i) {
if (dp[i + 1] > make_pair(dp[i].first + a[i], dp[i].second)) {
dp[i + 1] = make_pair(dp[i].first + a[i], dp[i].second);
}
if (dp[min(n, i + l)] > make_pair(dp[i].first + mid, dp[i].second + 1)) {
dp[min(n, i + l)] = make_pair(dp[i].first + mid, dp[i].second + 1);
}
}
return dp[n].second;
}
int solve() {
int l = 0, r = n;
int res = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (calc(mid) > k) {
l = mid + 1;
res = mid;
} else {
r = mid - 1;
}
}
if (calc(res) <= k) return 0;
calc(res + 1);
return dp[n].first - (res + 1) * 1ll * k;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> k >> l >> s;
for (int i = 0; i < n; ++i) {
a[i] = islower(s[i]) > 0;
}
int ans = INF;
ans = min(ans, solve());
for (int i = 0; i < n; ++i) {
a[i] = isupper(s[i]) > 0;
}
ans = min(ans, solve());
cout << ans << endl;
return 0;
}