Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
vector<int> l(3);
for (int i = 0; i < 3; ++i)
cin >> l[i];
bool ok = false;
for (int i = 0; i < 3; ++i)
ok |= l[i] == l[(i + 1) % 3] + l[(i + 2) % 3];
for (int i = 0; i < 3; ++i) if (l[i] % 2 == 0)
ok |= l[(i + 1) % 3] == l[(i + 2) % 3];
cout << (ok ? "YES\n" : "NO\n");
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n = int(input())
p = [int(x) for x in input().split()]
s = input()
l = sorted([[s[i], p[i], i] for i in range(n)])
q = [-1 for i in range(n)]
for i in range(n):
q[l[i][2]] = i + 1
print(*q)
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
typedef long long li;
const int INF = int(1e9);
const li INF64 = li(1e18);
int n;
li k;
vector<int> a;
inline bool read() {
if(!(cin >> n >> k))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
return true;
}
li accurateFloor(li a, li b) {
li val = a / b;
while (val * b > a)
val--;
return val;
}
inline void solve() {
sort(a.begin(), a.end());
vector<li> pSum(n + 1, 0);
fore (i, 0, n)
pSum[i + 1] = pSum[i] + a[i];
li ans = 1e18;
fore (y, 0, n) {
//(a[0] - x)(y + 1) + (pSum[n - y] - a[0]) <= k
//a[0] - x <= (k - pSum[n - y] + a[0]) / (y + 1)
//x == a[0] - (k - pSum[n - y] + a[0]) / (y + 1)
li x = a[0] - accurateFloor(k - pSum[n - y] + a[0], y + 1);
ans = min(ans, y + max(0LL, x));
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) {
read();
solve();
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int main()
{
int n;
cin >> n;
int k;
cin >> k;
string s;
cin >> s;
vector<int> p(n + 1);
for(int i = 0; i < n; i++) p[i + 1] = p[i] + (s[i] - '0');
vector<vector<int>> C(n + 1);
for(int i = 0; i <= n; i++)
{
C[i].resize(i + 1);
C[i][0] = C[i][i] = 1;
for(int j = 1; j < i; j++)
C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
}
int ans = 1;
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
{
int cnt = j + 1 - i;
int cnt1 = p[j + 1] - p[i];
if(cnt1 > k || p[n] < k) continue;
cnt -= 2;
if(s[i] == '0') cnt1--;
if(s[j] == '0') cnt1--;
if(cnt1 <= cnt && cnt1 >= 0 && cnt >= 0)
ans = add(ans, C[cnt][cnt1]);
}
cout << ans << endl;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
vector<int> x(n);
forn(i, n) scanf("%d", &x[i]);
vector<vector<int>> a(n, vector<int>(m));
forn(i, n) forn(j, m) scanf("%1d", &a[i][j]);
auto get = [&](int mask, vector<int>& p) {
};
int ans = -1;
vector<int> best;
forn(mask, 1 << n) {
vector<int> val(m);
forn(i, n) forn(j, m) if (a[i][j]) val[j] += ((mask >> i) & 1) ? +1 : -1;
int res = 0;
forn(i, n) res += ((mask >> i) & 1) ? -x[i] : x[i];
vector<int> p(m);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int x, int y) { return val[x] < val[y]; });
forn(i, m) res += val[p[i]] * (i + 1);
if (res > ans) ans = res, best = p;
}
vector<int> ansPerm(m);
forn(i, m) ansPerm[best[i]] = i;
forn(i, m) printf("%d ", ansPerm[i] + 1);
puts("");
}
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 * 1000 + 13;
using li = unsigned long long;
int pr[N];
li hs[N], f[N];
unordered_map<li, int> rf;
int main() {
int n;
scanf("%d", &n);
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
iota(pr, pr + N, 0);
for (int i = 2; i <= n; ++i) if (pr[i] == i) {
for (int j = i; j <= n; j += i) pr[j] = min(pr[j], i);
hs[i] = rnd();
}
for (int i = 2; i <= n; ++i) {
f[i] = f[i - 1];
int x = i;
while (x != 1) {
f[i] ^= hs[pr[x]];
x /= pr[x];
}
rf[f[i]] = i;
}
auto solve = [&] (int n) -> vector<int> {
li fp = 0;
for (int i = 2; i <= n; ++i) fp ^= f[i];
if (fp == 0) return {};
if (rf.count(fp)) return {rf[fp]};
for (int i = 2; i <= n; ++i) {
li x = f[i] ^ fp;
if (rf.count(x) && rf[x] != x) return {rf[x], i};
}
return {2, n / 2, n};
};
auto ans = solve(n);
printf("%d\n", n - (int)ans.size());
for (int i = 1; i <= n; ++i)
if (find(ans.begin(), ans.end(), i) == ans.end()) printf("%d ", i);
puts("");
}