Skip to content

Instantly share code, notes, and snippets.

@wiwiho
Last active Dec 12, 2020
Embed
What would you like to do?
NHSPC pre 2020
#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;
}
#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;
}
#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;
}
#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;
}
#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;
}
#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;
}
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment