Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int cnt1 = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
cnt1 += (x == 1);
}
cout << n - cnt1 / 2 << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
a1, a2, a3, a4 = map(int, input().split())
if a1 == 0:
print(1)
else:
print(a1 + min(a2, a3) * 2 + min(a1 + 1, abs(a2 - a3) + a4))
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> pos(n + 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
pos[x] = i;
}
int l = (n + 1) / 2, r = (n + 2) / 2;
while (l > 0 && (l == r || (pos[l] < pos[l + 1] && pos[r - 1] < pos[r]))) {
--l;
++r;
}
cout << (n - r + l + 1) / 2 << '\n';
}
}
1792D - Fixed Prefix Permutations
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
int get(const vector<int> &a, const vector<int> &b){
int res = 0;
while (res < int(a.size()) && a[res] == b[res])
++res;
return res;
}
int main(){
int t;
scanf("%d", &t);
while (t--){
int n, m;
scanf("%d%d", &n, &m);
vector<vector<int>> a(n, vector<int>(m));
forn(i, n) forn(j, m){
scanf("%d", &a[i][j]);
--a[i][j];
}
vector<vector<int>> b(n, vector<int>(m));
forn(i, n) forn(j, m) b[i][a[i][j]] = j;
sort(b.begin(), b.end());
forn(i, n){
int j = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
int ans = 0;
if (j > 0) ans = max(ans, get(a[i], b[j - 1]));
if (j < n) ans = max(ans, get(a[i], b[j]));
printf("%d ", ans);
}
puts("");
}
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (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())
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
int n;
li m1, m2;
inline bool read() {
if(!(cin >> n >> m1 >> m2))
return false;
return true;
}
vector<pt> mFact;
vector<li> divs;
void factM(li m1, li m2) {
mFact.clear();
for (int d = 2; d * d <= m1 || d * d <= m2; d++) {
int cnt = 0;
while (m1 % d == 0) {
m1 /= d;
cnt++;
}
while (m2 % d == 0) {
m2 /= d;
cnt++;
}
if (cnt > 0)
mFact.push_back({d, cnt});
}
if (m1 > m2)
swap(m1, m2);
if (m1 > 1)
mFact.push_back({m1, 1});
if (m2 > 1) {
if (m2 == m1)
mFact.back().y++;
else
mFact.push_back({m2, 1});
}
}
void genDivisors(int pos, li val) {
if (pos >= sz(mFact)) {
divs.push_back(val);
return;
}
li cur = val;
fore (pw, 0, mFact[pos].y + 1) {
genDivisors(pos + 1, cur);
if (pw < mFact[pos].y)
cur *= mFact[pos].x;
}
}
inline void solve() {
factM(m1, m2);
divs.clear();
genDivisors(0, 1);
sort(divs.begin(), divs.end());
vector<int> ans(sz(divs), 0);
vector<li> dp(sz(divs), -1);
fore (id, 0, sz(divs)) {
if (divs[id] <= n)
dp[id] = divs[id];
for (auto [p, pw] : mFact) {
if (divs[id] % p != 0)
continue;
int pos = int(lower_bound(divs.begin(), divs.end(), divs[id] / p) - divs.begin());
dp[id] = max(dp[id], dp[pos]);
}
if (divs[id] / dp[id] <= n)
ans[id] = divs[id] / dp[id];
}
int cnt = 0;
int xorSum = 0;
fore (i, 0, sz(ans)) {
cnt += ans[i] > 0;
xorSum ^= ans[i];
}
// cout << sz(ans) << endl;
// cout << ans << endl;
cout << cnt << " " << xorSum << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int t; cin >> t;
while (t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
1792F1 - Graph Coloring (easy version)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (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 mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int varMul(int x)
{
return x;
}
template<typename... Args>
int varMul(int x, Args... args)
{
return mul(x, varMul(args...));
}
int binpow(int x, int y)
{
int z = 1;
while(y)
{
if(y & 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
vector<int> fact, rfact;
vector<int> dp;
int n;
void precalc()
{
fact.resize(n + 1);
rfact.resize(n + 1);
fact[0] = 1;
for(int i = 1; i <= n; i++)
fact[i] = mul(i, fact[i - 1]);
for(int i = 0; i <= n; i++)
rfact[i] = binpow(fact[i], MOD - 2);
dp.resize(n + 1, -1);
}
int C(int n, int k)
{
if(n < 0 || n < k || k < 0) return 0;
return varMul(fact[n], rfact[k], rfact[n - k]);
}
int calc(int x)
{
if(dp[x] != -1) return dp[x];
if(x == 1) return dp[x] = 1;
if(x == 2) return dp[x] = 1;
dp[x] = 0;
int& d = dp[x];
for(int i = 1; i < x; i++)
{
d = add(d, varMul(calc(i), (i == x - 1 ? (MOD + 1) / 2 : calc(x - i)), 2, C(x - 1, i - 1)));
}
return d;
}
int main()
{
cin >> n;
precalc();
cout << add(mul(calc(n), 2), -2) << endl;
}
1792F2 - Graph Coloring (hard version)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int LOGN = 18;
const int N = (1 << LOGN);
const int MOD = 998244353;
const int g = 3;
#define forn(i, n) for(int i = 0; i < int(n); i++)
inline int mul(int a, int b)
{
return (a * 1ll * b) % MOD;
}
inline int norm(int a)
{
while(a >= MOD)
a -= MOD;
while(a < 0)
a += MOD;
return a;
}
inline int binPow(int a, int k)
{
int ans = 1;
while(k > 0)
{
if(k & 1)
ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
inline int inv(int a)
{
return binPow(a, MOD - 2);
}
vector<int> w[LOGN];
vector<int> iw[LOGN];
vector<int> rv[LOGN];
void precalc()
{
int wb = binPow(g, (MOD - 1) / (1 << LOGN));
for(int st = 0; st < LOGN; st++)
{
w[st].assign(1 << st, 1);
iw[st].assign(1 << st, 1);
int bw = binPow(wb, 1 << (LOGN - st - 1));
int ibw = inv(bw);
int cw = 1;
int icw = 1;
for(int k = 0; k < (1 << st); k++)
{
w[st][k] = cw;
iw[st][k] = icw;
cw = mul(cw, bw);
icw = mul(icw, ibw);
}
rv[st].assign(1 << st, 0);
if(st == 0)
{
rv[st][0] = 0;
continue;
}
int h = (1 << (st - 1));
for(int k = 0; k < (1 << st); k++)
rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
}
}
inline void fft(int a[N], int n, int ln, bool inverse)
{
for(int i = 0; i < n; i++)
{
int ni = rv[ln][i];
if(i < ni)
swap(a[i], a[ni]);
}
for(int st = 0; (1 << st) < n; st++)
{
int len = (1 << st);
for(int k = 0; k < n; k += (len << 1))
{
for(int pos = k; pos < k + len; pos++)
{
int l = a[pos];
int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k]));
a[pos] = norm(l + r);
a[pos + len] = norm(l - r);
}
}
}
if(inverse)
{
int in = inv(n);
for(int i = 0; i < n; i++)
a[i] = mul(a[i], in);
}
}
int aa[N], bb[N], cc[N];
vector<int> multiply(vector<int> a, vector<int> b)
{
int sza = a.size();
int szb = b.size();
int n = 1, ln = 0;
while(n < (sza + szb))
n <<= 1, ln++;
for(int i = 0; i < n; i++)
aa[i] = (i < sza ? a[i] : 0);
for(int i = 0; i < n; i++)
bb[i] = (i < szb ? b[i] : 0);
fft(aa, n, ln, false);
fft(bb, n, ln, false);
for(int i = 0; i < n; i++)
cc[i] = mul(aa[i], bb[i]);
fft(cc, n, ln, true);
int szc = n;
vector<int> c(szc);
szc = n;
for(int i = 0; i < n; i++)
c[i] = cc[i];
return c;
}
int main()
{
int n;
cin >> n;
vector<int> fact(n + 1);
fact[0] = 1;
for(int i = 0; i < n; i++)
fact[i + 1] = mul(fact[i], i + 1);
precalc();
vector<int> A = {0, 1, 2};
vector<int> B = {0, 1, 1};
vector<int> C = {0, 1, 1};
vector<int> D = {0, 1, 1};
vector<int> conv;
const int K = 2000;
int last_conv = -1e9;
while(A.size() <= n)
{
int cur = A.size();
if(cur - last_conv >= K)
{
last_conv = cur - 1;
conv = multiply(C, D);
}
/*for(auto x : conv) cerr << x << " ";
cerr << endl;*/
int val_A;
if(last_conv * 2 >= cur)
{
val_A = conv[cur];
// [cur - last_conv, last_conv] are already used
for(int i = 1; i < (cur - last_conv); i++)
{
val_A = norm(val_A + mul(C[i], D[cur - i]));
}
for(int i = last_conv + 1; i < cur; i++)
{
val_A = norm(val_A + mul(C[i], D[cur - i]));
}
}
else
{
val_A = 0;
for(int i = 1; i <= cur - 1; i++)
{
val_A = norm(val_A + mul(C[i], D[cur - i]));
}
}
val_A = mul(val_A, fact[cur - 1]);
val_A = mul(val_A, 2);
A.push_back(val_A);
B.push_back(mul(val_A, inv(2)));
C.push_back(mul(val_A, inv(fact[cur])));
D.push_back(mul(B.back(), inv(fact[cur - 1])));
}
cout << norm(A[n] - 2) << endl;
}