You can now find the contest in the public gym, ICPC-de-Tryst 2024 (the ghost submissions can still be accessed in the older mashup).
1. HR se puuch ke batayenge: rivalq, magga, Kira_1234
2. nulllösungssatz: Dominater069, aryanc403, IceKnight1093
3. 4C3: koderkushy, piyush_pransukhka, kingmessi
4. tbd: keyurchd_11, shiven, GenghizKhan
5. ElDiablo: ElDiablo
7. SmolBrain: SmolBrain
8. Pols_Station: Pols_Agyi_Pols
9. PalindORme: the_hyp0cr1t3, JeevanJyot, ExplodingFreeze
10. Team: jtnydv25
11. Cult Council: AKSLEGION, D1orite, shorya1835
12. IDK: ha___il, JadeReaper, akcube
13. ThreeMusketeers: gakshat468, sg0071729, 21cs01033
14. cns_lena_chahiye_tha: dhruvsomani, vikram108, ParadigmShift
1. ElDiablo: ElDiablo
2. Team: jtnydv25
3. monoid: htnaver, kayou81, atimanas
4. No clue: Beelzebub_blue
5. Death Valley: 1729_prism, Abhishek_821023, dark_ethics
We'll give prizes to the next 3 IITD teams not in the top 15.
A: ThreeMusketeers: gakshat468, sg0071729, 21cs01033
B: No clue: Beelzebub_blue
C: nulllösungssatz: Dominater069, aryanc403, IceKnight1093
D: HR se puuch ke batayenge: rivalq, magga, Kira_1234
E: nulllösungssatz: Dominater069, aryanc403, IceKnight1093
F: tbd: keyurchd_11, shiven, GenghizKhan
G: unforgettable playz: noobcodur, oviyan_gandhi, unforgettablepl
H: HR se puuch ke batayenge: rivalq, magga, Kira_1234
I: OverShadow: Coder_Nayak, Krypto_Ray, sloppy_coder
J: nulllösungssatz: Dominater069, aryanc403, IceKnight1093
K: nulllösungssatz: Dominater069, aryanc403, IceKnight1093
Setter: BladeRunner
//solution to Highly Constrained Permutation
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n; cin>>n;
vector<int> a(n+1),b(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
vector<vector<int>> adj(n+1);
//make graph in the forward direction first
vector<int> last(n+1);
for(int i=1;i<=n;i++)
{
//deal with last[a[i]-1] case
if(a[i]!=1)
{
if(last[a[i]-1]==0)
{
cout<<-1<<'\n';
return;
}
else adj[last[a[i]-1]].push_back(i);
}
//deal with the last[a[i]] case
if(last[a[i]] != 0) adj[i].push_back(last[a[i]]);
last[a[i]]=i;
}
//now in the backward direction
vector<int> next(n+1);
for(int i=n;i>=1;i--)
{
//deal with next[b[i]-1] case
if(b[i]!=1)
{
if(next[b[i]-1]==0)
{
cout<<-1<<'\n';
return;
}
else adj[i].push_back(next[b[i]-1]);
}
//deal with the next[b[i]] case
if(next[b[i]] != 0) adj[next[b[i]]].push_back(i);
next[b[i]]=i;
}
//so now toposort this graph
vector<bool> popped(n+1,false);
vector<int> indg(n+1);
queue<int> q;
// for(int i=1;i<=n;i++)
// {
// cout<<i<<'\n';
// for(auto j:adj[i]) cout<<j<<' ';
// cout<<'\n';
// }
for(int i=1;i<=n;i++)
{
for(auto j:adj[i]) indg[j]++;
}
for(int i=1;i<=n;i++)
{
if(indg[i]==0) q.push(i);
}
vector<int> order;
while(!q.empty())
{
int f=q.front();
q.pop();
popped[f]=true;
order.push_back(f);
for(auto nbr:adj[f])
{
indg[nbr]--;
if(indg[nbr]==0) q.push(nbr);
}
}
if((int)order.size() < n)
{
printf("%d\n",-1);
return;
}
vector<int> ans(n+1);
for(int i=0;i<n;i++) ans[order[i]]=i+1;
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
printf("\n");
}
signed main()
{
int t; cin>>t;
while(t--) solve();
}
Setter: 33_arsenic_75, Preparation: islingr
#include "bits/stdc++.h"
using namespace std;
int solve() {
int n, x;
cin >> n >> x;
const int msb = x >> 10 & 1;
if (msb == (n & 1)) return 10 * n;
return 10 * (n - 1) + 9;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) cout << solve() << '\n';
}
Setter: sahilkumar_1
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll rotate(ll x,ll base,vector <ll> & info){
if(x<base) return x;
int k=0;
for(int i=0;i<info.size();i++){
if(info[i]<=x&&info[i+1]>x){
k=i;
break;
}
}
return (info[k]*(x%base)+(x/base));
}
ll min_possible(ll x, ll base,vector <ll> & info){
if(x<base) return x;
ll ans=x;
for(int i=0;i<64;i++){
x=rotate(x,base,info);
ans=min(ans,x);
}
return ans;
}
void solve(vector <vector <ll>> & vect){
int n;
cin >> n;
ll sum=0;
for(int i=0;i<n;i++){
ll x;
cin>>x;
sum+=min_possible(x,i+3,vect[i+3]);
}
cout<<sum<<endl;
}
int main(){
int t;
cin >> t;
vector <vector <ll>> vect(1e5+3);
for(int i=3;i<=1e5+2;i++){
ll cur=1;
while(true){
vect[i].push_back(cur);
if(cur>1e9) break;
cur*=i;
}
}
while(t--) solve(vect);
}
Setter: ajmeraraghav99
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long int n,i,j;
cin>>n;
long long int marks[n+1];
int check[n+1];
for(i=1;i<=n;i++)
{
check[i]=0;
}
vector<int> v;
i=1;
while(i<=n)
{
if(v.size()==0)
{
v.push_back(i);
i++;
}
else
{
cout<<"? "<<v[v.size()-1]<<" "<<i<<endl;
fflush(stdout);
long long int x;
cin>>x;
marks[i]=abs(x);
check[i]=1;
if(x>0)
{
v.push_back(i);
}
else
{
v.pop_back();
}
i++;
}
}
int honest_index=v[v.size()-1];
vector<pair<long long,long long>> first_half;
for(i=1;i<=n;i++)
{
if(i!=honest_index)
{
if(check[i])
{
first_half.push_back({-marks[i],i});
}
else
{
cout<<"? "<<honest_index<<" "<<i<<endl;
fflush(stdout);
long long int dum;
cin>>dum;
marks[i]=abs(dum);
check[i]=1;
first_half.push_back({-marks[i],i});
}
}
}
sort(first_half.begin(),first_half.end());
int index=-1;
for(i=0;i<(n+1)/2;i++)
{
int dum_indx=first_half[i].second;
cout<<"? "<<honest_index<<" "<<dum_indx<<endl;
fflush(stdout);
long long int dum_marks;
cin>>dum_marks;
if(dum_marks>0)
{
index=dum_indx;
marks[index]=dum_marks;
break;
}
}
cout<<"? "<<index<<" "<<honest_index<<endl;
fflush(stdout);
long long smth;
cin>>smth;
marks[honest_index]=smth;
if(marks[honest_index]>marks[index])
{
cout<<"! "<<honest_index<<endl;
}
else
{
cout<<"! "<<index<<endl;
}
return 0;
}
Setter: Azm1t
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
void solve(){
int n, q; cin >> n >> q;
vector<int> c(n);
for(int &x: c) cin >> x, x--;
vector<vector<int>> adj(n);
for(int i = 0; i < n-1; i++){
int u, v; cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
ordered_set os[n];
vector<int> tin(n, 0), tout(n, 0);
int time = 0;
function<void(int, int)> dfs = [&](int v, int p){
tin[v] = time++;
for(int child: adj[v]){
if(child != p) dfs(child, v);
}
tout[v] = time++;
os[c[v]].insert({tin[v], v});
};
dfs(0, -1);
while(q--){
int type, v, x; cin >> type >> v >> x;
v--; x--;
if(type == 1){
os[c[v]].erase({tin[v], v});
c[v] = x;
os[c[v]].insert({tin[v], v});
}
else{
auto firstit = os[x].order_of_key({tin[v], -1});
auto lastit = os[x].order_of_key({tout[v], n+1});
cout << lastit - firstit << '\n';
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while(t--) solve();
}
Setter: PROELECTRO444
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int LOCATION = 4020;
const int MAXP = 1001;
const int SHIFT = 1010;
long long dp[MAXP][LOCATION];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n), p(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = 0; i < n; i++){
cin >> p[i];
}
for(int i = 0; i < n; i++){
dp[p[i]][a[i] + SHIFT] += 1ll;
if(p[i] != 0)
dp[p[i] — 1][a[i] + SHIFT] += 1ll;
}
for(int s = MAXP — 2; s >= 0; s--){
for(int i = 1; i < LOCATION — 1; i++){
dp[s][i] += dp[s + 1][i — 1] + dp[s + 1][i + 1] — (s + 2 < MAXP ? dp[s + 2][i] : 0);
}
}
for(int i = 0; i < MAXP; i++){
for(int j = 1; j < LOCATION; j++){
dp[i][j] += dp[i][j — 1];
}
}
while(q--){
int l, r, s;
cin >> l >> r >> s;
l += SHIFT;
r += SHIFT;
cout << dp[s][r] — dp[s][l — 1] << endl;
}
return 0;
}
Idea:PROELECTRO444 , BladeRunner Preparation: PROELECTRO444
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
bool solve(int s, int n, int k, int a[], int p[]){
vector<pair<int, int>> interval;
for (int i = 0; i < n; i++)
{
if (p[i] — s >= 0)
{
int left = a[i] — p[i] + s;
int right = a[i] + p[i] — s;
interval.push_back({left, 1});
interval.push_back({right + 1, -1});
}
}
sort(interval.begin(), interval.end());
int m = 0, sm = 0;
for (auto [_, v] : interval)
{
sm += v;
m = max(m, sm);
}
return m <= k;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
int a[n], p[n];
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> p[i];
int l = 0, r = 1e9 + 10;
while (l <= r){
int mid = (l + r) / 2;
if (solve(mid, n, k, a, p))
r = mid — 1;
else
l = mid + 1;
}
cout << l << endl;
}
}
Setter: islingr
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for (auto i{a}; i < (b); ++i)
#define per(i, a, b) for (auto i{b}; i-- > (a); )
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template <class T> bool uin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool uax(T& a, const T& b) { return a < b ? a = b, true : false; }
using ll = long long;
using poly = vector<ll>;
constexpr int mod = 998'244'353, root = 62;
int modpow(ll a, int b) {
ll res = 1;
for (; b; a = a * a % mod, b /= 2)
if (b & 1) res = res * a % mod;
return res;
}
void ntt(poly &a) {
int n = sz(a), L = 31 — __builtin_clz(n);
static poly rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
ll z[] = {1, modpow(root, mod >> s)};
rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
}
vector<int> rev(n);
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
a[i + j + k] = ai — z + (z > ai ? mod : 0);
ai += (ai + z >= mod ? z — mod : z);
}
}
poly conv(const poly &a, const poly &b) {
if (a.empty() || b.empty()) return {};
int s = sz(a) + sz(b) — 1, B = 32 — __builtin_clz(s),
n = 1 << B;
int inv = modpow(n, mod — 2);
poly L(a), R(b), out(n);
L.resize(n), R.resize(n);
ntt(L), ntt(R);
rep(i,0,n)
out[-i & (n — 1)] = (ll)L[i] * R[i] % mod * inv % mod;
ntt(out);
return {out.begin(), out.begin() + s};
}
poly operator*(const poly& a, const poly& b) {
return conv(a, b);
}
constexpr int N = 2e5 + 10;
ll fac[N];
ll mul(ll x, ll y) { return x * y % mod; }
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
fac[0] = 1;
rep(i, 1, N) fac[i] = mul(i, fac[i - 1]);
int n;
cin >> n;
vector<ll> a(n);
for (auto& x : a) cin >> x;
poly T(n);
for (int s = 1; s < n; ++s)
T[s] = mul(fac[s - 1], fac[n - s - 1]);
vector<ll> score(n);
auto rec = [&](const auto& self, int l, int r, const poly& T) -> poly {
if (r - l == 1) {
poly P;
if (l == n - 1) P = {0, 1};
else P = {1, a[l + 1]};
score[l] = (T[0] * P[0] + T[1] * P[1]) % mod;
return P;
}
const int mid = l + (r - l) / 2;
const poly Tr(T.begin(), T.begin() + (r - mid + 1));
auto Pr = self(self, mid, r, Tr);
reverse(all(Pr));
auto Tl = Pr * T;
Tl.erase(Tl.begin(), Tl.begin() + (r - mid));
reverse(all(Pr));
const auto Pl = self(self, l, mid, Tl);
return Pl * Pr;
};
rec(rec, 1, n, T);
const auto to_div = modpow(fac[n - 1], mod - 2);
rep(i, 1, n) score[i] = mul(to_div, mul(i, mul(a[i], score[i])));
score[0] = 1;
for (auto x : a) score[0] = mul(score[0], x);
rep(i, 0, n) cout << score[i] << " \n"[i == n - 1];
}
Setter: Surver
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n, k, m;
cin >> n >> k >> m;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
vector<pair<int, int>> q(m);
for (int i = 0; i < m; i++) {
cin >> q[i].first >> q[i].second;
}
vector<int> ans(m);
auto calc = [&] () {
vector<vector<int>> suf(n + 1, vector<int>(k + 1));
for (int i = n — 1; i >= 0; i--) {
suf[i] = suf[i + 1];
int cost = 0, sum = 0;
for (int j = i; j < n; j++) {
cost += (v[j] > 0);
sum -= abs(v[j]);
if (cost <= k) {
suf[i][cost] = min(suf[i][cost], sum);
}
}
for (int j = 1; j <= k; j++) {
suf[i][j] = min(suf[i][j], suf[i][j — 1]);
}
}
vector<int> dp(n + 1, 1);
vector<int> h(n + 1, k + 1);
h[0] = 0;
for (int i = 0; i <= n; i++) {
if (i > 0) {
int cost = 0, sum = 0;
for (int j = i — 1; j >= 0; j--) {
cost += (v[j] < 0);
sum += abs(v[j]);
h[sum] = min(h[sum], cost);
}
}
for (int j = 0; j <= n; j++) {
if (h[j] <= k) {
dp[j] = min(dp[j], suf[i][k — h[j]]);
}
}
}
for (int i = 0; i < m; i++){
for (int j = 0; j <= n; j++){
if (dp[j] <= 0){
ans[i] = max(ans[i], q[i].first * j — q[i].second * dp[j]);
}
}
}
};
calc();
reverse(v.begin(), v.end());
calc();
for (int i = 0; i < m; i++){
cout << ans[i] << " \n"[i == m — 1];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Setter: BladeRunner
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+100;
const int mod = 1e9+7;
vector<int> fact(N+1);
vector<int> ifact(N+1);
int binexp(int a,int n)
{
if(n==0) return 1;
else
{
int res=binexp(a,n/2);
res=(res*res)%mod;
if(n&1) res=(res*a)%mod;
return res;
}
}
int ncr(int n,int r)
{
if(r>n || r<0 || n<0) return 0;
int ans=(fact[n]*ifact[r])%mod;
ans=(ans*ifact[n-r])%mod;
return ans;
}
void solve()
{
int n,x,y; cin>>n>>x>>y;
int dif=abs(x-y);
cout<<ncr(n-2,dif-1)<<'\n';
}
signed main()
{
int t; cin>>t;
fact[0]=1;
for(int i=1;i<=N;i++) fact[i]=(fact[i-1]*i)%mod;
ifact[N]=binexp(fact[N],mod-2);
for(int i=N-1;i>=0;i--) ifact[i]=(ifact[i+1]*(i+1))%mod;
while(t--) solve();
}
Setter: MridulAhi
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for (auto i{a}; i < (b); ++i)
#define per(i, a, b) for (auto i{b}; i-- > (a); )
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template <class T> bool uin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool uax(T& a, const T& b) { return a < b ? a = b, true : false; }
using ll = long long;
using U = uint32_t;
using poly = vector<ll>;
constexpr int mod = 998'244'353, root = 62;
int modpow(ll a, int b) {
ll res = 1;
for (; b; a = a * a % mod, b /= 2)
if (b & 1) res = res * a % mod;
return res;
}
void ntt(poly &a) {
int n = sz(a), L = 31 — __builtin_clz(n);
static poly rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
ll z[] = {1, modpow(root, mod >> s)};
rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
}
vector<int> rev(n);
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
a[i + j + k] = ai — z + (z > ai ? mod : 0);
ai += (ai + z >= mod ? z — mod : z);
}
}
poly conv(const poly &a, const poly &b) {
if (a.empty() || b.empty()) return {};
int s = sz(a) + sz(b) — 1, B = 32 — __builtin_clz(s),
n = 1 << B;
int inv = modpow(n, mod — 2);
poly L(a), R(b), out(n);
L.resize(n), R.resize(n);
ntt(L), ntt(R);
rep(i,0,n)
out[-i & (n — 1)] = (ll)L[i] * R[i] % mod * inv % mod;
ntt(out);
return {out.begin(), out.begin() + s};
}
constexpr int N = 1e5;
ll mul(ll x, ll y) { return x * y % mod; }
int fac[N], ifac[N];
int C(int n, int r) { return mul(fac[n], mul(ifac[r], ifac[n — r])); }
int solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> g(k);
rep(e, 0, m) {
char a, b;
cin >> a >> b;
const int u = a - 'a', v = b - 'a';
g[u].push_back(v);
g[v].push_back(u);
}
vector Q(k + 1, poly(n + 1, 0));
for (int t = 1; t <= k; ++t)
for (int r = t; r <= n; ++r)
Q[t][r] = mul(ifac[r], C(r - 1, t - 1));
auto merge = [&](const poly& a, const poly& b) {
auto c = conv(a, b);
c.resize(n + 1, 0);
return c;
};
ll res = 0;
vector<poly> f(1 << k);
f[0].assign(n + 1, 0);
f[0][0] = 1;
rep(S, 1u, 1u << k) {
const auto root = 31 ^ __builtin_clz(S);
assert(S >> root & 1);
U T = 0;
{
auto dfs = [&](const auto& self, int u) -> void {
T |= 1u << u;
for (auto v : g[u])
if ((~T & S) >> v & 1)
self(self, v);
};
dfs(dfs, root);
}
const int t = popcount(T);
f[S] = merge(f[S ^ T], Q[t]);
res += f[S][n];
}
return mul(res % mod, fac[n]);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
fac[0] = 1;
rep(i, 1, N) fac[i] = mul(i, fac[i - 1]);
ifac[N - 1] = modpow(fac[N - 1], mod - 2);
per(i, 1, N) ifac[i - 1] = mul(i, ifac[i]);
int t;
cin >> t;
while (t--) cout << solve() << '\n';
}