NHSPC pre 2020

A_Apple_Orange.cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<vector<ll>> cnt(2, vector<ll>(2));
    ll ans = 0;

    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        cnt[a % 2][b % 2]++;
    }
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            ans += cnt[i][j] * (cnt[i][j] - 1) / 2;
        }
    }
    cout << ans << "\n";

    return 0;
}

B_Sphinx.cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    ll sum = 0;
    vector<ll> r(n), c(m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            ll a;
            cin >> a;
            sum += a;
            r[i] += a;
            c[j] += a;
        }
    }

    bool ok = sum == 0;
    for(int i = 0; i < n; i++){
        if(r[i] != 0) ok = false;
    }
    for(int i = 0; i < m; i++){
        if(c[i] != 0) ok = false;
    }

    if(ok) cout << "Yes\n";
    else cout << "No\n";

    return 0;
}

C_Elliptic.cpp

#include <bits/stdc++.h>

#define eb emplace_back
#define pll pair<ll, ll>
#define mp make_pair
#define F first
#define S second
#define topos(a) ((a) = ((a) % MOD + MOD) % MOD)
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())

using namespace std;

typedef long long ll;

ll MOD;

ll fp(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

vector<ll> invv;

ll inv(ll a){
    return invv[a % MOD];
}

vector<pll> ans;

void add(ll w, ll z){
    ans.eb(mp(w * inv(z) % MOD, inv(z)));
    //cerr << w << " " << z << " " << inv(z) << " " << ans.back().F << " " << ans.back().S << "\n";
}

vector<vector<ll>> rt;

void solve(ll a, ll b, ll c, ll w){
    if(a == 0 && b == 0 && c == 0){
        for(int i = 0; i < MOD; i++) add(w, i);
        return;
    }
    if(a == 0 && b == 0){
        return;
    }
    if(a == 0){
        ll ans = -c * inv(b) % MOD;
        topos(ans);
        add(w, ans);
        return;
    }

    ll tmp = b * b % MOD - 4 * a % MOD * c % MOD;
    tmp %= MOD;
    topos(tmp);
    //cerr << tmp << "\n";
    for(ll i : rt[tmp]){
        //cerr << "rt " << i << "\n";
        ll z = (i - b) * inv(2 * a) % MOD;
        topos(z);
        add(w, z);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ll A, B, C, D, E, F, G, H, I, p;
    cin >> A >> B >> C >> D >> E >> F >> G >> H >> I >> p;
    MOD = p;
    rt.resize(p);
    invv.resize(p);
    for(int i = 0; i < p; i++){
        invv[i] = fp(i, MOD - 2);
    }

    if(MOD == 2){
    
        for(ll x = 0; x < MOD; x ++){
            for(ll y = 0; y < MOD; y++){
                ll tmp = 0;
                tmp += A * x % MOD * x % MOD * x % MOD;
                tmp += B * x % MOD * x % MOD * y % MOD;
                tmp += C * x % MOD * y % MOD * y % MOD;
                tmp += D * y % MOD * y % MOD * y % MOD;
                tmp += E * x % MOD * x % MOD;
                tmp += F * x % MOD * y % MOD;
                tmp += G * y % MOD * y % MOD;
                tmp += H * x % MOD;
                tmp += I * y % MOD;
                tmp %= MOD;
                if(tmp == 0) ans.eb(mp(x, y));
            }
        }

        lsort(ans);
        uni(ans);
        for(pll i : ans) cout << i.F << " " << i.S << "\n";
        return 0;

    }

    for(ll i = 0; i < p; i++){
        rt[i * i % MOD].eb(i);
    }

    for(ll x = 0; x < p; x++){
        ll tmp = A * x % MOD * x % MOD * x % MOD + E * x % MOD * x % MOD + H * x % MOD;
        tmp %= MOD;
        if(tmp == 0) ans.eb(mp(x, 0));
    }

    for(ll w = 0; w < p; w++){
        ll a = H * w % MOD + I;
        a %= MOD;
        ll b = E * w % MOD * w % MOD + F * w % MOD + G;
        b %= MOD;
        ll c = A * w % MOD * w % MOD * w % MOD + B * w % MOD * w % MOD + C * w % MOD +D;
        c %= MOD;
        //cerr << w << " " << a << " " << b << " " << c << "\n";
        solve(a, b, c, w);
    }

    lsort(ans);
    uni(ans);

    for(pll i : ans) cout << i.F << " " << i.S << "\n";

    return 0;
}

D_Tower.cpp

#include <bits/stdc++.h>

#define eb emplace_back
#define pll pair<ll, ll>
#define mp make_pair
#define F first
#define S second
#define topos(a) ((a) = ((a) % MOD + MOD) % MOD)
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())

using namespace std;

typedef long long ll;

struct SparseTable{
    vector<vector<int>> st;
    int t = 0;

    int f(int a, int b){
        return t ? max(a, b) : min(a, b);
    }
    
    void build(int n, vector<int>& a, int tt){
        t = tt;
        st.resize(n, vector<int>(20));
        for(int i = 0; i < n; i++) st[i][0] = a[i];
        for(int i = 1; i < 20; i++){
            for(int j = 0; j + (1 << i) - 1 < n; j++){
                st[j][i] = f(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
            }
        }
    }

    int query(int l, int r){
        int lg = __lg(r - l + 1);
        return f(st[l][lg], st[r - (1 << lg) + 1][lg]);
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<int> h(n);
    for(int i = 0; i < n; i++) cin >> h[i];

    SparseTable mxst, mnst;
    mxst.build(n, h, 1);
    mnst.build(n, h, 0);

    ll ans = 0;
    for(int i = 0; i < n; i++){
        int l = i, r = n - 1;
        while(l < r){
            int m = (l + r + 1) / 2;
            if(mxst.query(i, m) - mnst.query(i, m) > k) r = m - 1;
            else l = m;
        }
        //cerr << i << " " << l<< "\n";
        ans += l - i + 1;
    }

    cout << ans << "\n";

    return 0;
}

E_Entanglement.cpp

#include <bits/stdc++.h>

#define eb emplace_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define topos(a) ((a) = ((a) % MOD + MOD) % MOD)
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())

using namespace std;

typedef long long ll;

vector<vector<int>> g;
vector<int> vst;

int fd = -1, f = -1;

void dfs(int now, int p, int dpt){
    vst[now] = 1;
    if(dpt > fd){
        fd = dpt;
        f = now;
    }
    for(int i : g[now]){
        if(i == p) continue;
        if(vst[i] == 2) continue;
        if(vst[i] == 1){
            cout << "INF\n";
            exit(0);
        }
        dfs(i, now, dpt + 1);
    }
    vst[now] = 2;
}

void dfs2(int now, int p, int dpt){
    if(dpt > fd){
        fd = dpt;
        f = now;
    }
    for(int i : g[now]){
        if(i == p) continue;
        dfs2(i, now, dpt + 1);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> G(n);
    for(int i = 0; i < n; i++) cin >> G[i];
    vector<vector<vector<pii>>> eg(2001, vector<vector<pii>>(2001));
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < n; j++){
            int t = s[j] - '0';
            if(!t) continue;
            eg[G[i]][G[j]].eb(mp(i, j));
        }
    }

    int m;
    cin >> m;
    vector<int> H(m);
    for(int i = 0; i < m; i++) cin >> H[i];
    vector<vector<vector<pii>>> eh(2001, vector<vector<pii>>(2001));
    for(int i = 0; i < m; i++){
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            int t = s[j] - '0';
            if(!t) continue;
            eh[H[i]][H[j]].eb(mp(i, j));
        }
    }

    vector<bool> ok(n * m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(G[i] == H[j]) ok[i * m + j] = true;
        }
    }
    
    g.resize(n * m);
    vst.resize(n * m);
    int cnt = 0;
    for(int i = 1; i <= 2000; i++){
        for(int j = 1; j <= 2000; j++){
            for(pii e1 : eg[i][j]){
                for(pii e2 : eh[i][j]){
                    int v1 = e1.F * m + e2.F;
                    int v2 = e1.S * m + e2.S;
                    if(v1 > v2) continue;
                    cnt++;
                    g[v1].eb(v2);
                    g[v2].eb(v1);
                    //cerr << v1 << " " << v2 << "\n";
                    if(cnt > n * m - 1){
                        cout << "INF\n";
                        return 0;
                    }
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < n * m; i++){
        if(vst[i] || !ok[i]) continue;
        //cerr << "test " << i << "\n";
        f = -1, fd = -1;
        dfs(i, i, 1);
        int tmp = f;
        f = -1, fd = -1;
        dfs2(tmp, tmp, 1);
        ans = max(ans, fd);
    }
    cout << ans << "\n";

    return 0;
}

F_Alarm_Clock.cpp

#include <bits/stdc++.h>

#define eb emplace_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define topos(a) ((a) = ((a) % MOD + MOD) % MOD)
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())

using namespace std;

typedef long long ll;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];

    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1));
    for(int i = 1; i <= n; i++) dp[i][i] = a[i];
    for(int len = 1; len < n; len++){
        for(int l = 1; l + len <= n; l++){
            int r = l + len;
            ll mnp = l, mn = a[l];
            for(int i = l + 1; i <= r; i++){
                if(a[i] < mn) mn = a[i], mnp = i;
            }
            for(int i = max((ll)k + 1, mnp - k); i <= min((ll)n - k, mnp + k); i++){
                ll tmp = mn * (min(i + k, r) - max(i - k, l) + 1);
                if(i - k - 1 >= l) tmp += dp[l][i - k - 1];
                if(i + k + 1 <= r) tmp += dp[i + k + 1][r];
                //cerr << l << " " << r << " " << i << " " << tmp << "\n";
                dp[l][r] = max(dp[l][r], tmp);
            }
        }
    }
   
    cout << dp[1][n] << "\n";

    return 0;
}

G_Fence(2).cpp

#include <bits/stdc++.h>

#define eb emplace_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define topos(a) ((a) = ((a) % MOD + MOD) % MOD)
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define pdd pair<ld, ld>

using namespace std;

typedef long long ll;
typedef double ld;


template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ld PI = acos(-1);

ld atanqq(ld y, ld x){
    ld ans = atan2(y, x);
    if(ans < 0) ans += PI;
    return ans;
}

vector<ld> ot;

pdd rotate(pdd p, ld rt){
    ld x = p.F, y = p.S;
    ld r = sqrt(x * x + y * y);
    ld t = atanqq(y, x);
    t += rt;
    ld ny = r * sin(t);
    ld nx = r * cos(t);
    //cerr << p << " " << rt << " " << mp(nx,ny) << "\n";
    return mp(nx, ny);
}

ld calc(pdd p, ld nx, ld r, int id){
    ld x = p.F, y = p.S;
    ld st = nx / r;
    ld t = acos(st);
    return t - ot[id];
}

bool check(ld mnt, ld mxt, vector<pdd>& p, ld d){
    ld mn = mnt, mx = mxt;
    for(int ii = 0; ii < p.size(); ii++){
        pdd i = p[ii];
        ld x = i.F, y = i.S;
        ld r = sqrt(x * x + y * y);
        if(r < d) continue;
        ld t1 = calc(i, d, r, ii), t2 = calc(i, -d, r, ii);
        //cerr << i << " " << d << " " << t1 << " " << t2 << "\n";
        mx = min(mx, t2);
        mn = max(mn, t1);
    }
    return mn <= mx;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t1 = clock();

    int n;
    cin >> n;

    ld mnt = -2 * PI, mxt = 2 * PI;
    vector<pdd> p(n);
    ld l = 0, r = 0;
    ot.resize(n);
    for(int i = 0; i < n; i++){
        ld x, y;
        cin >> x >> y;
        p[i] = mp(x, y);
        ld t = atanqq(y, x);
        mnt = max(mnt, -t);
        mxt = min(mxt, PI - t);
        r = max(r, abs(x));
        ot[i] = t;
    }
    //cerr << l << " " << r << "\n";

    while(l + max(l * 1e-9, 1e-8) < r){
        int t2 = clock();
        if(t2 - t1 >= 0.96 * CLOCKS_PER_SEC) break;
        ld m = (l + r) / 2;
        if(check(mnt, mxt, p, m)) r = m;
        else l = m;
    }

    cout << fixed << setprecision(20) << (l + r) * 2 << "\n";

    return 0;
}