Skip to content

Instantly share code, notes, and snippets.

@koosaga
Last active Sep 16, 2017
Embed
What would you like to do?
ACM-ICPC Daejeon Regional 2016
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
int cnt[10005], n;
int main(){
cin >> n;
int sum = 0;
for(int i=0; i<n; i++){
int x;
scanf("%d",&x);
cnt[x]++;
sum += x;
}
if(sum != n * (n-1) / 2){
puts("-1");
return 0;
}
int t = n;
for(int i=n-1; i; i--){
while(cnt[i]){
int tmp[10005] = {};
cnt[i]--;
int d = t-1-i;
for(int j=i; j && d; j--){
int w = min(d, cnt[j]);
cnt[j] -= w;
tmp[j-1] += w;
d -= w;
}
if(d){
puts("-1");
return 0;
}
for(int j=0; j<=i; j++) cnt[j] += tmp[j];
t--;
}
}
puts("1");
}
#include <cstdio>
#include <algorithm>
#include <bitset>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
int k, n;
pi a[1000005];
int cnt[1000005], cur;
void add(int x){
if (!cnt[x]) cur++;
cnt[x]++;
}
void del(int x){
cnt[x]--;
if (!cnt[x]) cur--;
}
int half(int x){
if (x < 0) return (x - 1) / 2;
return x / 2;
}
int main(){
scanf("%d %d", &k, &n);
for (int i = 0; i < n; i++){
scanf("%d %d", &a[i].first, &a[i].second);
}
sort(a, a + n);
int e = 0;
int dap = 1e9, pos = -1;
for (int i = 0; i < n; i++){
while (e < n && cur < k){
add(a[e++].second);
}
if (cur == k){
int p = half(a[i].first + a[e-1].first);
int rad = max(a[e - 1].first - p, p - a[i].first);
if (dap > rad){
dap = rad;
pos = p;
}
}
del(a[i].second);
}
printf("%d", pos);
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
typedef pair<int, int> pi;
string str;
string sym[1005];
vector<int> gph[1005];
vector<string> spl;
int nxt;
void solve(int s, int e, int rt){
if (s > e){
puts("ERROR");
exit(0);
}
int bracket = 0;
for (int i = e; i >= s; i--){
if (str[i] == '(') bracket--;
if (str[i] == ')') bracket++;
if (bracket != 0) continue;
if (str[i] == '+' || str[i] == '-'){
sym[rt] = str.substr(i, 1);
nxt++;
gph[rt].push_back(nxt);
solve(s, i - 1, nxt);
nxt++;
gph[rt].push_back(nxt);
solve(i + 1, e, nxt);
return;
}
}
bracket = 0;
for (int i = e; i >= s; i--){
if (str[i] == '(') bracket--;
if (str[i] == ')') bracket++;
if (bracket != 0) continue;
if (str[i] == '*' || str[i] == '/'){
sym[rt] = str.substr(i, 1);
nxt++;
gph[rt].push_back(nxt);
solve(s, i - 1, nxt);
nxt++;
gph[rt].push_back(nxt);
solve(i + 1, e, nxt);
return;
}
}
if (str[s] == '('){
if (str[e] != ')'){
puts("ERROR");
exit(0);
}
solve(s + 1, e - 1, rt);
return;
}
for (int i = s; i <= e; i++){
if (str[i] < '0' || str[i] > '9'){
puts("ERROR");
exit(0);
}
}
sym[rt] = str.substr(s, e - s + 1);
return;
}
string dfs(int root){
if (gph[root].size() == 0) return sym[root];
if (gph[root].size() != 2){
puts("ERROR");
exit(0);
}
string ret = dfs(gph[root][0]) + " " + dfs(gph[root][1]) + " " + sym[root];
spl.push_back(ret);
return ret;
}
int main(){
while (1){
char t = getchar();
if (t == -1) break;
if (t == ' ' || t == '\n') continue;
str.push_back(t);
}
solve(0, str.size() - 1, 0);
dfs(0);
sort(spl.begin(), spl.end(), [&](const string &a, const string &b){
int c1 = count(a.begin(), a.end(), ' ');
int c2 = count(b.begin(), b.end(), ' ');
if (c1 != c2) return c1 > c2;
return a < b;
});
for (int i = 0; i < spl.size() - 1; i++){
if (spl[i] == spl[i + 1]){
cout << spl[i] << endl;
return 0;
}
}
puts("ERROR");
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int oo = 1e9;
struct bd{
int s, e, h, idx;
bool operator<(const bd &c)const{
return s < c.s;
}
}a[100005], b[100005];
lint ccw(pi a, pi b, pi c){
int dx1 = b.first - a.first;
int dy1 = b.second - a.second;
int dx2 = c.first - a.first;
int dy2 = c.second - a.second;
return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
int n;
pi c[200005], d[200005];
struct seg{
vector<pi> tree[530000];
int lim;
void get_hull(vector<pi> &v){
vector<pi> w = v;
v.clear();
for(auto &i : w){
while(v.size() >= 2 && ccw(v[v.size()-2], v.back(), i) >= 0){
v.pop_back();
}
v.push_back(i);
}
}
bool inside(int n, int x, int y, int dx, int dy){
assert(!tree[n].empty());
int s = 0, e = tree[n].size() - 1;
auto func = [&](const int idx){
return 1ll * dx * (tree[n][idx].second - y) - 1ll * dy * (tree[n][idx].first - x);
};
while(s != e){
int m = (s+e)/2;
if(func(m) > func(m+1)) e = m;
else s = m+1;
}
return func(s) >= 0;
}
void init(pi *a, int n){
for(lim = 1; lim <= n; lim <<= 1);
for(int i=0; i<n; i++){
for(int j=lim+i; j; j>>=1){
tree[j].push_back(a[i]);
}
}
for(int j=1; j<lim+n; j++){
get_hull(tree[j]);
}
}
int query(int x, int y, int dx, int dy){
int pos = 1;
while(pos < lim){
if(inside(2 * pos, x, y, dx, dy)) pos *= 2;
else pos = pos * 2 + 1;
}
return pos - lim;
}
}seg[2];
int query(bd *a, pi *b, int t, int x, int y, int dx, int dy){
int j = seg[t].query(x, y, dx, dy);
if(j == 2*n) return 0;
if(j % 2 == 1) return a[j/2].idx;
if(ccw(pi(x, y), pi(x + dx, y + dy), pi(b[j].first, 0)) > 0){
return 0;
}
return a[j/2].idx;
}
int main(){
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%d %d %d",&a[i].s, &a[i].e, &a[i].h);
a[i].idx = i+1;
}
sort(a, a+n);
for(int i=0; i<n; i++){
b[i] = a[n-1-i];
tie(b[i].s, b[i].e) = pi(-b[i].e, -b[i].s);
c[2*i] = pi(a[i].s, a[i].h);
c[2*i+1] = pi(a[i].e, a[i].h);
}
for(int i=0; i<2*n; i++){
d[i] = c[2*n-1-i];
d[i].first *= -1;
}
c[2*n] = d[2*n] = pi(1e9 + 5, 1e9 + 5);
seg[0].init(c, 2*n+1);
seg[1].init(d, 2*n+1);
int q; scanf("%d",&q);
while(q--){
int x, y, dx, dy;
scanf("%d %d %d %d",&x,&y,&dx,&dy);
if(dx == 0){
int pos = lower_bound(c, c+2*n, pi(x, -1)) - c;
if(pos % 2 == 0 && c[pos].first != x){
puts("0");
}
else{
printf("%d\n", a[pos/2].idx);
}
continue;
}
else if(dx < 0){
printf("%d\n", query(b, d, 1, -x, y, -dx, dy));
}
else{
printf("%d\n", query(a, c, 0, x, y, dx, dy));
}
}
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
char s[1005][1005];
bool vis[1005][1005];
int n, m;
int dfs(int x, int y){
if(vis[x][y]) return 0;
vis[x][y] = 1;
if(x == n-1) return 1;
for(int i=0; i<4; i++){
if(x + dx[i] >= n || x + dx[i] < 0 || y + dy[i] >= m || y + dy[i] < 0 ||
s[x+dx[i]][y+dy[i]] == '1') continue;
if(dfs(x + dx[i], y + dy[i])){
return 1;
}
}
return 0;
}
int main(){
cin >> n >> m;
for(int i=0; i<n; i++) cin >> s[i];
for(int i=0; i<m; i++){
if(s[0][i] == '0' && dfs(0, i)){
puts("YES");
return 0;
}
}
puts("NO");
}
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int m, n;
int main(){
cin >> m >> n;
int px = 0, py = 0;
int d = 0;
while(n--){
string w;
int x;
cin >> w >> x;
if(w == "MOVE"){
px += x * dx[d];
py += x * dy[d];
if(max(px, py) > m || min(px, py) < 0){
cout << -1;
return 0;
}
}
else{
if(x == 0){
d = (d+1) % 4;
}
else{
d = (d+3) % 4;
}
}
}
cout << px << " " << py;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
struct pnt{
int x, y, v;
bool operator<(const pnt &p)const{
return pi(x, y) < pi(p.x, p.y);
}
bool operator==(const pnt &p)const{
return x == p.x && y == p.y && v == p.v;
}
bool operator!=(const pnt &p)const{
return !(*this == p);
}
}a[500005];
void ensure(bool p){
if(!p){
puts("-1");
exit(0);
}
}
lint solve(pnt a, pnt b){
return abs(a.x - b.x) + abs(a.y - b.y);
}
int n;
int main(){
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].v);
}
sort(a, a+n);
lint ret = 0;
for(int t=0; t<2; t++){
pnt nul = {0, 0, -1};
pnt lo = nul, hi = nul;
for(int i=0; i<n; i++){
if(i == 0){
ensure(a[i].v == 1);
continue;
}
if(i == n-1){
ensure(lo != nul && hi != nul);
ensure(lo.y < a[i].y && a[i].y < hi.y);
ret += solve(a[i], lo) + solve(a[i], hi);
break;
}
if(a[i].v == 0){
ensure(lo == nul || hi == nul);
if(lo == nul) lo = a[i];
else hi = a[i];
if(hi.y < lo.y) swap(lo, hi);
}
else{
ensure(lo != nul || hi != nul);
if(lo == nul){
ensure(a[i].y != hi.y);
ret += solve(a[i], hi);
hi = nul;
continue;
}
if(hi == nul){
ensure(a[i].y != lo.y);
ret += solve(a[i], lo);
lo = nul;
continue;
}
if(a[i].y > hi.y){
ret += solve(a[i], hi);
hi = nul;
}
else if(a[i].y < lo.y){
ret += solve(a[i], lo);
lo = nul;
}
else if(lo.y < a[i].y && a[i].y < hi.y){
if(a[i+1].v == 1){
if(a[i+1].y < a[i].y){
ret += solve(a[i+1], lo) + solve(a[i], hi);
lo = hi = nul;
}
else if(a[i+1].y > a[i].y){
ret += solve(a[i], lo) + solve(a[i+1], hi);
lo = hi = nul;
}
else ensure(0);
}
else{
if(a[i+1].y > a[i].y){
ensure(a[i+1].y < hi.y);
ret += solve(a[i], lo);
lo = a[i+1];
}
else if(a[i+1].y < a[i].y){
ensure(a[i+1].y > lo.y);
ret += solve(a[i], hi);
hi = a[i+1];
}
else ensure(0);
}
i++;
}
else ensure(0);
}
}
reverse(a, a+n);
}
cout << ret;
}
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef long long lint;
const int MAXN = 444;
struct maxflow{
struct edg{int pos, cap, rev;};
vector<edg> gph[MAXN];
void clear(){
for(int i=0; i<MAXN; i++){
gph[i].clear();
}
}
void add_edge(int s, int e, int x){
gph[s].push_back({e, x, (int)gph[e].size()});
gph[e].push_back({s, 0, (int)gph[s].size()-1});
}
int dis[MAXN], pnt[MAXN];
bool bfs(int src, int sink){
memset(dis, 0, sizeof(dis));
memset(pnt, 0, sizeof(pnt));
queue<int> que;
que.push(src);
dis[src] = 1;
while(!que.empty()){
int x = que.front();
que.pop();
for(int i=0; i<gph[x].size(); i++){
edg e = gph[x][i];
if(e.cap > 0 && !dis[e.pos]){
dis[e.pos] = dis[x] + 1;
que.push(e.pos);
}
}
}
return dis[sink] > 0;
}
int dfs(int x, int sink, int f){
if(x == sink) return f;
for(; pnt[x] < gph[x].size(); pnt[x]++){
edg e = gph[x][pnt[x]];
if(e.cap > 0 && dis[e.pos] == dis[x] + 1){
int w = dfs(e.pos, sink, min(f, e.cap));
if(w){
gph[x][pnt[x]].cap -= w;
gph[e.pos][e.rev].cap += w;
return w;
}
}
}
return 0;
}
lint match(int src, int sink){
lint ret = 0;
while(bfs(src, sink)){
int r;
while((r = dfs(src, sink, 2e9))) ret += r;
}
return ret;
}
};
struct circ{
maxflow mf;
lint lsum;
void clear(){
lsum = 0;
mf.clear();
}
void add_edge(int s, int e, int l, int r){
lsum += l;
mf.add_edge(s + 2, e + 2, r - l);
mf.add_edge(0, e + 2, l);
mf.add_edge(s + 2, 1, l);
}
bool solve(int s, int e){
mf.add_edge(e+2, s+2, 1e9);
return lsum == mf.match(0, 1);
}
int get(int s, int e){
s += 2;
e += 2;
for(auto &j : mf.gph[s]){
if(j.pos == e) return j.cap;
}
assert(0);
}
}circ;
int n, m;
int a[205][205], s1[205], s2[205];
void in(int &x){
double y;
scanf("%lf",&y);
x = (int)round(10 * y);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
in(a[i][j]);
}
in(s1[i]);
}
for(int i=1; i<=m; i++) in(s2[i]);
int ls = 0;
circ.clear();
for(int i=1; i<=n; i++){
circ.add_edge(0, i, s1[i] / 10, (s1[i] + 9) / 10);
}
for(int i=1; i<=m; i++){
circ.add_edge(i + n, n + m + 1, s2[i] / 10, (s2[i] + 9) / 10);
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
circ.add_edge(i, j + n, a[i][j] / 10, (a[i][j] + 9) / 10);
}
}
assert(circ.solve(0, n+m+1));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
printf("%d ", (a[i][j] + 9) / 10 - circ.get(i, j + n));
}
printf("%d\n", (s1[i] + 9) / 10 - circ.get(0, i));
}
for(int i=1; i<=m; i++){
printf("%d ", (s2[i] + 9) / 10 - circ.get(i+n, n+m+1));
}
}
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int L[1050000], R[1050000];
int dfs(int v){
if (v == 0) return 0;
return min(dfs(L[v]), dfs(R[v])) + 1;
}
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++){
scanf("%d %d", &L[i], &R[i]);
}
printf("%d", dfs(1));
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
int dep[2222222], n;
int mx[2222222];
int main(){
scanf("%d",&n);
for(int i=2; i<(2<<n); i++){
scanf("%d",&dep[i]);
}
lint ret = 0;
for(int i=(1<<n)-1; i; i--){
mx[i] = max(mx[2*i] + dep[2*i], mx[2*i+1] + dep[2*i+1]);
ret += 2 * mx[i] - mx[2*i] - mx[2*i+1];
}
printf("%lld\n", ret);
}
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int MAXN = 5005;
int n;
pi a[MAXN];
int pfx[MAXN], sfx[MAXN];
int dist(pi a, pi b){
int x = b.first - a.first, y = b.second - a.second;
return x * x + y * y;
}
int main(){
scanf("%d",&n);
for(int i=0; i<n; i++) scanf("%d %d",&a[i].first,&a[i].second);
int st = 0, cur = -1;
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
int nxt = dist(a[i], a[j]);
if(nxt > cur){
cur = nxt;
st = i;
}
}
}
swap(a[0], a[st]);
sort(a + 1, a + n, [&](const pi &p, const pi &q){
return dist(a[0], p) < dist(a[0], q);
});
for(int i=0; i<n; i++){
for(int j=0; j<i; j++) pfx[i] = max(pfx[i], dist(a[i], a[j]));
for(int j=i+1; j<n; j++) sfx[i] = max(sfx[i], dist(a[i], a[j]));
}
for(int i=1; i<n; i++){
pfx[i] = max(pfx[i], pfx[i-1]);
sfx[n-1-i] = max(sfx[n-1-i], sfx[n-i]);
}
double ans = 1e9;
for(int i=0; i<n-1; i++) ans = min(ans, sqrt(pfx[i]) + sqrt(sfx[i + 1]));
printf("%.10f\n", ans);
}
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
lint segment_distance(pair<pi, pi> a, pair<pi, pi> b){
pi s1 = a.first, e1 = a.second, s2 = b.first, e2 = b.second;
if (s1.second == e1.second){
swap(s1.first, s1.second);
swap(e1.first, e1.second);
swap(s2.first, s2.second);
swap(e2.first, e2.second);
}
if (s1 > e1) swap(s1, e1);
if (s2 > e2) swap(s2, e2);
if (s2.first == e2.first){
int dx = abs(s2.first - s1.first);
int dy = 0;
if (max(s1.second, s2.second) <= min(e1.second, e2.second)){
dy = 0;
}
else{
dy = min(abs(e1.second - s2.second), abs(e2.second - s1.second));
}
return dx * dx + dy * dy;
}
else{
int dx = 0, dy = 0;
if (s1.second <= s2.second && s2.second <= e1.second){
dy = min(abs(s2.first - s1.first), abs(e2.first - s1.first));
return dy * dy;
}
if (s2.first <= s1.first && s1.first <= e2.first){
dy = min(abs(s2.second - s1.second), abs(s2.second - e1.second));
return dy * dy;
}
dx = min({ abs(s1.first - s2.first), abs(s1.first - e2.first), abs(e1.first - s2.first), abs(e1.first - e2.first) });
dy = min({ abs(s1.second - s2.second), abs(s1.second - e2.second), abs(e1.second - s2.second), abs(e1.second - e2.second)});
return dx * dx + dy * dy;
}
}
int a, b, c, l;
pi pnt[10005];
vector<pair<pi, pi>> sega, segb, segc;
lint dist[10005];
bool vis[10005];
int main(){
scanf("%*d %*d %d %d %d %d", &a, &b, &c, &l);
for (int i = 0; i < a; i++){
scanf("%d %d", &pnt[i].first, &pnt[i].second);
if (i > 0) sega.emplace_back(pnt[i - 1], pnt[i]);
}
for (int i = 0; i < b; i++){
scanf("%d %d", &pnt[i].first, &pnt[i].second);
if (i > 0) segb.emplace_back(pnt[i - 1], pnt[i]);
}
for (int i = 0; i < c; i++){
pi a, b;
scanf("%d %d %d %d", &a.first, &a.second, &b.first, &b.second);
segc.emplace_back(a, b);
}
lint ret = 1e18;
for (auto &i : sega){
for (auto &j : segb){
ret = min(ret, segment_distance(i, j));
}
}
if (ret > l){
ret = 1e18;
}
memset(dist, 0x3f, sizeof(dist));
for (auto &i : sega){
for (int j = 0; j < segc.size(); j++){
lint k = segment_distance(i, segc[j]);
if (k <= l){
dist[j] = min(dist[j], k);
}
}
}
for (int i = 0; i < segc.size(); i++){
lint cur = 1e18, pos = -1;
for (int j = 0; j < segc.size(); j++){
if (!vis[j] && dist[j] < cur){
cur = dist[j];
pos = j;
}
}
if (pos == -1) break;
vis[pos] = 1;
for (auto &j : segb){
lint w = segment_distance(segc[pos], j);
if (w <= l) ret = min(ret, w + dist[pos]);
}
for (int j = 0; j < segc.size(); j++){
lint w = segment_distance(segc[pos], segc[j]);
if (w <= l && j != pos)
dist[j] = min(dist[j], dist[pos] + w);
}
}
if (ret > 1e16){
ret = -1;
}
printf("%lld", ret);
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
int n, d;
const int mod = 31991;
struct mat{
int adj[55][55];
mat operator*(const mat &m)const{
mat ret;
for(int i=0; i<d; i++){
for(int j=0; j<d; j++){
ret.adj[i][j] = 0;
for(int k=0; k<d; k++){
ret.adj[i][j] += adj[i][k] * m.adj[k][j];
ret.adj[i][j] %= mod;
}
}
}
return ret;
}
}ret, piv;
int main(){
cin >> d >> n;
for(int i=0; i<d; i++){
ret.adj[i][i] = 1;
piv.adj[0][i] = 1;
}
for(int i=1; i<d; i++){
piv.adj[i][i-1] = 1;
}
while(n){
if(n&1) ret = ret * piv;
piv = piv * piv;
n >>= 1;
}
cout << ret.adj[0][0];
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 100005;
lint ccw(pi a, pi b, pi c){
int dx1 = b.first - a.first;
int dy1 = b.second - a.second;
int dx2 = c.first - a.first;
int dy2 = c.second - a.second;
return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
pi cur;
struct seg{
pi s, e;
int idx;
double func(){
int a = e.second - s.second;
int b = s.first - e.first;
lint c = 1ll * a * s.first + 1ll * b * s.second;
return c / (a * (1.0 * cur.first / cur.second) + b);
}
};
struct event{
pi p;
int x, y;
bool operator<(const event &ev)const{
return ccw(pi(0, 0), p, ev.p) > 0;
}
};
vector<pi> v[MAXN];
vector<event> ev;
int chk[MAXN];
int main(){
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++){
int k;
scanf("%d",&k);
v[i].resize(k);
for(auto &j : v[i]) scanf("%d %d",&j.first,&j.second);
auto cmp = [&](const pi &a, const pi &b){
return ccw(pi(0, 0), a, b) > 0;
};
rotate(v[i].begin(), max_element(v[i].begin(), v[i].end(), cmp), v[i].end());
int m = min_element(v[i].begin(), v[i].end(), cmp) - v[i].begin();
v[i].resize(m + 1);
reverse(v[i].begin(), v[i].end());
for(int j=0; j<v[i].size(); j++){
ev.push_back({v[i][j], i, j});
}
}
sort(ev.begin(), ev.end());
auto cmp = [](seg a, seg b){
return a.func() < b.func();
};
set<seg, decltype(cmp)> s(cmp);
for(int ii=0; ii + 1<ev.size(); ii++){
event i = ev[ii], j = ev[ii + 1];
if(i.y != 0){
seg t = (seg){v[i.x][i.y-1], v[i.x][i.y], i.x};
auto x = s.lower_bound(t);
if(x != s.end() && x->idx == i.x) s.erase(x);
else s.erase(--x);
}
cur = pi(i.p.first + j.p.first, i.p.second + j.p.second);
if(i.y != v[i.x].size() - 1){
s.insert({v[i.x][i.y], v[i.x][i.y + 1], i.x});
}
if(!s.empty()) chk[s.begin()->idx] = 1;
}
cout << count(chk + 1, chk + n + 1, 0);
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
int n, a, b, d2[10005];
short dp[10005][10005];
char str[10005];
bool ok(int s, int e){
int m = dp[s][e];
return 2 * m * b >= a * (e-s+1);
}
int main(){
cin >> n >> a >> b >> str;
for(int i=1; i<n; i++){
for(int j=0; j+i<n; j++){
if(str[j] == str[j+i]) dp[j][j+i] = dp[j+1][j+i-1] + 1;
}
}
for(int i=1; i<=n; i++){
d2[i] = 1e9;
for(int j=0; j<i; j++){
if(ok(j, i-1)) d2[i] = min(d2[i], d2[j] + 1);
}
}
if(d2[n] > 1e8) d2[n] = 0;
cout << d2[n];
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 5005;
vector<int> gph[MAXN];
set<pi> s;
void dfs(int x, int y){
if(s.find(pi(x, y)) != s.end()) return;
s.insert(pi(x, y));
int l = find(gph[y].begin(), gph[y].end(), x) - gph[y].begin() + 1;
l %= gph[y].size();
dfs(y, gph[y][l]);
}
int solve2(){
int n;
scanf("%d",&n);
int edg = 0;
for(int i=1; i<=n; i++){
int x;
scanf("%d",&x);
gph[i].resize(x);
for(auto &j : gph[i]) scanf("%d",&j);
edg += x;
}
edg /= 2;
if(edg > 20000) return -1;
int ans = 0;
for(int i=1; i<=n; i++){
for(int j=0; j<gph[i].size(); j++){
if(s.find(pi(i, gph[i][j])) == s.end()){
dfs(i, gph[i][j]);
ans++;
}
}
}
return n - edg + ans == 2 ? 1 : -1;
}
void add_edge(int s, int e){
gph[s].push_back(e);
gph[e].push_back(s);
}
bool has_edge(int s, int e){
return find(gph[s].begin(), gph[s].end(), e) != gph[s].end();
}
void del_edge(int s, int e){
gph[s].erase(find(gph[s].begin(), gph[s].end(), e));
gph[e].erase(find(gph[e].begin(), gph[e].end(), s));
}
int solve1(){
int n, m;
scanf("%d %*d %d",&n,&m);
for(int i=0; i<m; i++){
int s, e;
scanf("%d %d",&s,&e);
add_edge(s, e);
}
queue<int> que;
for(int i=1; i<=n; i++){
if(gph[i].size() == 2){
que.push(i);
}
}
while(!que.empty()){
int x = que.front();
que.pop();
if(gph[x].size() != 2) continue;
int l = gph[x][0];
int r = gph[x][1];
if(l == r) return -1;
del_edge(l, x);
del_edge(r, x);
add_edge(l, r);
if(gph[l].size() == 2) que.push(l);
if(gph[r].size() == 2) que.push(r);
}
vector<int> vtx;
for(int i=1; i<=n; i++){
if(gph[i].size()) vtx.push_back(i);
}
if(vtx.size() == 5){
for(auto &i : vtx){
if(gph[i].size() != 4) return -1;
}
for(int i=0; i<vtx.size(); i++){
for(int j=0; j<i; j++){
if(!has_edge(vtx[i], vtx[j])) return -1;
}
}
return 1;
}
if(vtx.size() == 6){
for(auto &i : vtx){
if(gph[i].size() != 3) return -1;
}
sort(vtx.begin(), vtx.end());
int ans = -1;
do{
bool ok = 1;
for(int i=0; i<3; i++){
for(int j=3; j<6; j++){
if(!has_edge(vtx[i], vtx[j])) ok = 0;
}
}
if(ok) ans = 1;
}while(next_permutation(vtx.begin(), vtx.end()));
return ans;
}
return -1;
}
int main(){
int q;
scanf("%d",&q);
if(q == -1) printf("%d\n", solve1());
else printf("%d\n", solve2());
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, lint> pi;
const int MAXN = 3005;
struct maxflow{
struct edg{int pos, cap, rev;};
vector<edg> gph[MAXN];
void clear(){for(int i=0; i<MAXN; i++) gph[i].clear();}
void add_edge(int s, int e, int x){
gph[s].push_back({e, x, (int)gph[e].size()});
gph[e].push_back({s, 0, (int)gph[s].size()-1});
}
int dis[MAXN], pnt[MAXN];
bool bfs(int src, int sink){
memset(dis, 0, sizeof(dis));
memset(pnt, 0, sizeof(pnt));
queue<int> que;
que.push(src);
dis[src] = 1;
while(!que.empty()){
int x = que.front();
que.pop();
for(auto &e : gph[x]){
if(e.cap > 0 && !dis[e.pos]){
dis[e.pos] = dis[x] + 1;
que.push(e.pos);
}
}
}
return dis[sink] > 0;
}
int dfs(int x, int sink, int f){
if(x == sink) return f;
for(; pnt[x] < gph[x].size(); pnt[x]++){
edg e = gph[x][pnt[x]];
if(e.cap > 0 && dis[e.pos] == dis[x] + 1){
int w = dfs(e.pos, sink, min(f, e.cap));
if(w){
gph[x][pnt[x]].cap -= w;
gph[e.pos][e.rev].cap += w;
return w;
}
}
}
return 0;
}
lint match(int src, int sink){
lint ret = 0;
while(bfs(src, sink)){
int r;
while((r = dfs(src, sink, 2e9))) ret += r;
}
return ret;
}
}mf;
struct circ{
maxflow mf;
lint lsum;
void clear(){
lsum = 0;
mf.clear();
}
void add_edge(int s, int e, int l, int r){
lsum += l;
mf.add_edge(s + 2, e + 2, r - l);
mf.add_edge(0, e + 2, l);
mf.add_edge(s + 2, 1, l);
}
bool solve(int s, int e){
mf.add_edge(e+2, s+2, 1e9); // to reduce as maxflow with lower bounds, in circulation problem skip this line
return lsum == mf.match(0, 1);
// to get maximum LR flow, run maxflow from s+2 to e+2 again
}
}circ;
int n, m, s, e;
pi vp[105];
vector<int> idx[105];
vector<pi> itv[105];
int main(){
cin >> n >> m >> s >> e;
tie(s, e) = pi(m-e, m-s);
for(int i=0; i<m; i++){
int s, e;
cin >> s >> e;
vp[i] = pi(n-e, n-s);
}
int ptr = n;
for(int i=0; i<n; i++){
int k;
cin >> k;
idx[i].resize(k);
itv[i].resize(k);
circ.add_edge(0, i+1, s, e);
for(int j=0; j<k; j++){
int s, e, d;
cin >> d >> s >> e;
idx[i][j] = ++ptr;
itv[i][j] = pi(s, e);
circ.add_edge(i+1, idx[i][j], d, e - s + 1);
}
}
for(int i=0; i<n; i++){
for(int j=0; j<itv[i].size(); j++){
for(int k=itv[i][j].first; k<=itv[i][j].second; k++){
circ.add_edge(idx[i][j], ptr + k, 0, 1);
}
}
}
for(int i=0; i<m; i++){
circ.add_edge(ptr + i + 1, ptr + m + 1, vp[i].first, vp[i].second);
}
if(!circ.solve(0, ptr + m + 1)){
puts("-1");
return 0;
}
puts("1");
for(int i=0; i<n; i++){
vector<int> v;
for(auto &j : idx[i]){
for(auto &k : circ.mf.gph[j+2]){
if(k.pos > ptr+2 && k.cap == 0){
v.push_back(k.pos - ptr - 2);
}
}
}
sort(v.begin(), v.end());
printf("%d ", v.size());
for(auto &i : v) printf("%d ", i);
puts("");
}
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, lint> pi;
int n, a[1005];
int main(){
cin >> n;
for(int i=0; i<n; i++) cin >> a[i];
sort(a, a+n);
for(int i=0; i<=n; i++){
bool ok1 = 0, ok2 = 0;
if(i == 0 || a[n-i] >= i) ok1 = 1;
if(i == n || a[n-i-1] <= i) ok2 = 1;
if(ok1 && ok2){
printf("%d ", i);
}
}
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
int n, s[100005], e[100005], l;
map<int, int> mp;
int main(){
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%d %d",&s[i],&e[i]);
if(s[i] > e[i]) swap(s[i], e[i]);
}
scanf("%d",&l);
for(int i=0; i<n; i++){
if(e[i] - s[i] > l) continue;
tie(s[i], e[i]) = pi(e[i] - l, s[i]);
mp[2*s[i]]++;
mp[2*e[i]+1]--;
}
int dap = 0, ret = 0;
for(auto &i : mp){
ret += i.second;
dap = max(dap, ret);
}
cout << dap;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, lint> pi;
int n, w, l, a[1005];
int dp[1005];
int main(){
cin >> n >> w >> l;
for(int i=1; i<=n; i++) cin >> a[i];
deque<int> dq;
for(int i=0; i<w; i++) dq.push_back(0);
int sum = 0, ret = 0, pnt = 1;
while(pnt <= n){
sum -= dq.front();
dq.pop_front();
if(a[pnt] + sum <= l){
dq.push_back(a[pnt]);
sum += a[pnt];
pnt++;
}
else{
dq.push_back(0);
}
ret++;
}
cout << ret + w;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment