Skip to content

Instantly share code, notes, and snippets.

@ftiasch

ftiasch/A.cpp

Last active July 28, 2016 13:15
Show Gist options
  • Save ftiasch/de118fbac5f86bad7d754fa1675dc4b8 to your computer and use it in GitHub Desktop.
Save ftiasch/de118fbac5f86bad7d754fa1675dc4b8 to your computer and use it in GitHub Desktop.
Download ZIP
2016 Multi-University Training Contest 4 team170
Raw
README.md

2016 Multi-University Training Contest 4 team170

Raw
A.cpp
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<iomanip>
#include<complex>
#include<utility>
using namespace std;
char s[100101],t[100101];
int nxt[100101];
int ans[100101];
int dp[100101];
const int mod=1000000007;
int T;
int main(){
dp[0]=1;
scanf("%d",&T);
for(int tt=1;tt<=T;++tt){
scanf("%s%s",s+1,t+1);
int N=strlen(s+1),M=strlen(t+1);
for(int i=2;i<=M;++i){
int j=nxt[i-1];
while(j&&t[j+1]!=t[i]) j=nxt[j];
if(t[j+1]==t[i]) nxt[i]=j+1;
else nxt[i]=0;
}
for(int i=1;i<=N;++i){
int j=ans[i-1];
dp[i]=dp[i-1];
while(j&&s[i]!=t[j+1]) j=nxt[j];
if(s[i]==t[j+1]) ans[i]=j+1;
else ans[i]=0;
if(ans[i]==M){
ans[i]=nxt[ans[i]];
dp[i]+=dp[i-M];
if(dp[i]>=mod) dp[i]-=mod;
}
}
printf("Case #%d: %d\n",tt,dp[N]);
}
return 0;
}
Raw
B.cpp
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<iomanip>
#include<complex>
#include<utility>
using namespace std;
int T,N;
vector<int> V[100100];
int cntv[100100];
int st[100100];
int ed[100100];
int links[100100];
int same[100100][3];
int fa[100100];
int A[100100];
int ans[100100];
int anss[100100];
bool solved;
int stand[100100];
inline bool Cmp(){
for(int i=1;i<=N;++i) if(ans[i]!=anss[i]) return anss[i]<ans[i];
return false;
}
bool checkFa(int L,int R){
bool flag=true;
for(int i=L;i<R;++i){
if(fa[links[i]]!=links[i+1]){
flag=false;
break;
}
}
if(flag) return true;
flag=true;
reverse(links+L,links+R+1);
for(int i=L;i<R;++i){
if(fa[links[i]]!=links[i+1]){
flag=false;
break;
}
}
return flag;
}
void checkRoot(int R){
fa[R]=-1;
{
stack<int> S;
S.push(R);
while(!S.empty()){
int x=S.top();
S.pop();
for(int i=0;i<int(V[x].size());++i) if(V[x][i]!=fa[x]){
if(A[V[x][i]]>A[x]) return;
fa[V[x][i]]=x;
S.push(V[x][i]);
}
}
}
for(int i=1;i<=N;++i) if(cntv[i]&&!checkFa(st[i],ed[i])) return;
{
priority_queue<int> PQ;
for(int i=N;i>=1;--i){
if(!cntv[i]){
if(PQ.empty()) return;
anss[PQ.top()]=i;
PQ.pop();
}
else{
anss[links[st[i]]]=i;
for(int j=st[i]+1;j<=ed[i];++j) PQ.push(links[j]);
}
}
}
if(!solved||Cmp()){
for(int i=1;i<=N;++i) ans[i]=anss[i];
solved=true;
}
}
void solve(){
solved=false;
for(int i=1;i<=N;++i){
++cntv[A[i]];
for(int j=0;j<int(V[i].size());++j){
if(A[V[i][j]]==A[i]){
if(same[i][0]==2){
printf(" Impossible\n");
return;
}
same[i][++same[i][0]]=V[i][j];
}
}
if(stand[A[i]]==-1||same[stand[A[i]]][0]>same[i][0]){
stand[A[i]]=i;
}
}
st[0]=1,ed[0]=0;
for(int i=1;i<=N;++i){
st[i]=ed[i-1]+1,ed[i]=ed[i-1];
if(stand[i]==-1) continue;
{
int pre=-1;
int now=stand[i];
int len=0;
int nxt=-1;
do{
links[++ed[i]]=now;
nxt=-1;
for(int j=1;j<=same[now][0];++j) if(same[now][j]!=pre){
nxt=same[now][j];
}
++len;
pre=now;
now=nxt;
}while(now!=-1);
if(len!=cntv[i]){
printf(" Impossible\n");
return;
}
}
}
if(cntv[N]==0){
printf(" Impossible\n");
return;
}
{
int f=links[st[N]],g=links[ed[N]];
checkRoot(f);
if(f!=g) checkRoot(g);
}
if(!solved){
printf(" Impossible\n");
}
else{
for(int i=1;i<=N;++i) printf(" %d",ans[i]);
printf("\n");
}
}
int main(){
scanf("%d",&T);
for(int tt=1;tt<=T;++tt){
scanf("%d",&N);
for(int i=1;i<=N;++i) V[i].clear(),same[i][0]=0,cntv[i]=0,stand[i]=-1;
for(int i=1;i<=N;++i) scanf("%d",A+i);
for(int i=1;i<N;++i){
int x,y;
scanf("%d%d",&x,&y);
V[x].push_back(y);
V[y].push_back(x);
}
printf("Case #%d:",tt);
solve();
}
return 0;
}
Raw
C.cpp
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<iomanip>
#include<complex>
#include<utility>
using namespace std;
int nei[21];
int T,N,M;
int cnt[1048580];
int tot;
int inv[1048580];
int e[400][2];
bool bfs(int mask){
if(!mask) return false;
int nmask=mask&-mask;
int qmask=mask&-mask;
while(qmask){
int f=inv[qmask&-qmask];
qmask^=1<<f;
int fmask=(nmask|nei[f])&mask;
qmask|=fmask^nmask;
nmask=fmask;
}
return nmask==mask;
}
void dfs(int st,int op1,int op2){
if(st==N){
if(bfs(op1)&&bfs(op2)){
++tot;
++cnt[op1];
++cnt[op2];
}
return;
}
dfs(st+1,op1|(1<<st),op2);
dfs(st+1,op1,op2|(1<<st));
}
int main(){
for(int i=0;i<20;++i) inv[1<<i]=i;
scanf("%d",&T);
for(int tt=1;tt<=T;++tt){
scanf("%d%d",&N,&M);
tot=0;
for(int i=0;i<N;++i) nei[i]=0;
for(int i=0;i<M;++i){
int x,y;
scanf("%d%d",&x,&y);
nei[x]|=1<<y;
nei[y]|=1<<x;
e[i][0]=x,e[i][1]=y;
}
for(int i=0;i<(1<<N);++i) cnt[i]=0;
dfs(1,1,0);
for(int i=1;i<(1<<N);i<<=1){
for(int j=0;j<(1<<N);++j){
if(j&i) cnt[j^i]+=cnt[j];
}
}
printf("Case #%d:",tt);
for(int i=0;i<M;++i) printf(" %d",tot-cnt[(1<<e[i][0])|(1<<e[i][1])]);
printf("\n");
}
return 0;
}
Raw
D_part.cpp
#include <cstdio>
#include <cstring>
const int MOD = (int)1e9 + 7;
void update(int& x, int a)
{
x += a;
if (x >= MOD) {
x -= MOD;
}
}
const int N = 20;
int t, ways[2][1 << N + 1];
int inverse(int a)
{
return a == 1 ? 1 : (long long)(MOD - MOD / a) * inverse(MOD % a) % MOD;
}
void gao(int n, int i, int must = -1)
{
for (int j = 0; j < n; ++ j) {
t ^= 1;
memset(ways[t], 0, sizeof(*ways[t]) << n + 1);
for (int msk_ = 0; msk_ < 1 << n + 1; ++ msk_) {
int msk = j ? msk_ : msk_ << 1;
if (ways[t ^ 1][msk_]) {
update(ways[t][msk & ~(1 << j)], ways[t ^ 1][msk_]);
if (j && !(msk >> j - 1 & 7) && (j < n - 1 || must != 0)) {
update(ways[t][msk | 7 << j - 1], ways[t ^ 1][msk_]);
}
}
}
}
}
int solve(int n)
{
int n2 = n + 2 >> 1;
memset(ways[t], 0, sizeof(*ways[t]) << n + 1);
ways[t][0] = 1;
for (int i = 0; i < n2; ++ i) {
gao(n, i);
}
int result = 0;
for (int msk_ = 0; msk_ < 1 << n + 1; ++ msk_) {
bool valid = true;
for (int i = 0; i < n; ++ i) {
valid &= (msk_ >> i & 1) == (msk_ >> n - 1 - i & 1);
}
if (valid) {
update(result, ways[t][msk_]);
}
}
for (int i = n2; i < n; ++ i) {
gao(n, i);
}
for (int msk_ = 0; msk_ < 1 << n + 1; ++ msk_) {
update(result, ways[t][msk_]);
}
return (long long)result * inverse(4) % MOD;
}
int result[N + 1];
int main()
{
for (int n = 1; n <= N; ++ n) {
result[n] = solve(n);
}
int T;
scanf("%d", &T);
for (int t = 1; t <= T; ++ t) {
int n;
scanf("%d", &n);
printf("Case #%d: %d\n", n, result[n]);
}
}
Raw
E.cpp
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<iomanip>
#include<complex>
#include<utility>
using namespace std;
int T;
int N;
long long L,R;
int P[16][2];
long long ans;
long long powMod(long long a,long long b,long long P){
a%=P;
long long ret=1;
while(b){
if(b&1) if(P<=(ret*=a)) ret%=P;
if(P<=(a*=a)) a%=P;
b>>=1;
}
return ret;
}
long long getV(long long x,long long mod,long long rem){
if(x<rem) return 0;
return (x-rem)/mod+1;
}
void solve(long long mod,long long rem,int st,int add){
ans+=add*(getV(R,mod,rem)-getV(L,mod,rem));
for(int i=st;i<=N;++i){
long long inv=powMod(mod,P[i][0]-2,P[i][0]);
long long diff=P[i][1]-rem%P[i][0];
if(diff<0) diff+=P[i][0];
inv=inv*diff%P[i][0];
solve(mod*P[i][0],rem+mod*inv,i+1,-add);
}
}
int main(){
scanf("%d",&T);
for(int tt=1;tt<=T;++tt){
scanf("%d%I64d%I64d",&N,&L,&R),--L;
for(int i=1;i<=N;++i){
scanf("%d%d",P[i],P[i]+1);
}
ans=0;
solve(7,0,1,1);
printf("Case #%d: %I64d\n",tt,ans);
}
return 0;
}
Raw
F.cpp
#include <cstdio>
#include <cstring>
#include <iostream>
const int N = 100000;
const int C = 26;
char buffer[N + 1];
struct State {
int length;
State *parent;
State* go[C];
State* extend(State*, int);
};
int state_count;
State states[N * 2 + 1];
State* new_state(int length)
{
State* n = states + (state_count ++);
n->length = length;
n->parent = NULL;
memset(n->go, 0, sizeof(n->go));
return n;
}
State* State::extend(State* start, int token) {
State *p = this;
State *np = new_state(length + 1);
while (p && !p->go[token]) {
p->go[token] = np;
p = p->parent;
}
if (!p) {
np->parent = start;
} else {
State *q = p->go[token];
if (p->length + 1 == q->length) {
np->parent = q;
} else {
State *nq = new_state(p->length + 1);
memcpy(nq->go, q->go, sizeof(q->go));
nq->parent = q->parent;
np->parent = q->parent = nq;
while (p && p->go[token] == q) {
p->go[token] = nq;
p = p->parent;
}
}
}
return np;
}
int main()
{
int T;
scanf("%d", &T);
for (int t = 1; t <= T; ++ t) {
scanf("%s", buffer);
char x = *buffer;
scanf("%s", buffer);
state_count = 0;
State* root = new_state(0);
long long result = 0;
State* p = root;
int last = -1;
for (int i = 0; buffer[i]; ++ i) {
if (buffer[i] == x) {
last = i;
}
p = p->extend(root, buffer[i] - 'a');
result += i + 1 - std::max(p->parent->length, i - last);
}
std::cout << "Case #" << t << ": " << result << std::endl;
}
}
Raw
G.cpp
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <climits>
#include <utility>
#include <vector>
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const int N = 100000;
int n, dfs_count, position[N], size[N], same[N];
std::vector<int> tree[N];
std::vector<std::pair<int, int> > starts[N];
void prepare(int p, int u)
{
position[u] = dfs_count ++;
size[u] = 1;
foreach (iterator, tree[u]) {
int v = *iterator;
if (v != p) {
prepare(u, v);
starts[u].push_back(std::make_pair(position[v], v));
size[u] += size[v];
}
}
}
typedef std::pair<int, int> Interval;
bool is_ancestor_of(int a, int d)
{
return position[a] <= position[d] && position[d] + size[d] <= position[a] + size[a];
}
std::vector<Interval> get_intervals(int from, int to)
{
std::vector<Interval> result;
if (is_ancestor_of(from, to)) {
std::vector<std::pair<int, int> >& start = starts[from];
std::vector<std::pair<int, int> >::iterator iterator = std::upper_bound(start.begin(), start.end(), std::make_pair(position[to], INT_MAX));
iterator --;
int v = iterator->second;
result.push_back(std::make_pair(0, position[v]));
result.push_back(std::make_pair(position[v] + size[v], n));
} else {
result.push_back(std::make_pair(position[from], position[from] + size[from]));
}
return result;
}
struct Event
{
Event(int y1, int y2, int w) : y1(y1), y2(y2), w(w)
{
}
int y1, y2, w;
};
std::vector<Event> events[N + 1];
void add_events(const std::vector<Interval>& begins, const std::vector<Interval>& ends, int weight)
{
foreach (b, begins)
{
foreach (e, ends)
{
//printf("[%d, %d) * [%d, %d) = %d\n", b->first, b->second, e->first, e->second, weight);
events[b->first].push_back(Event(e->first, e->second, weight));
events[b->second].push_back(Event(e->first, e->second, -weight));
}
}
}
int delta[N << 1], maximum[N << 1];
int get_id(int l, int r)
{
return l + r | l != r;
}
void cover(int l, int r, int a, int b, int c)
{
if (b < l || r < a) {
return;
}
int id = get_id(l, r);
if (a <= l && r <= b) {
delta[id] += c;
maximum[id] += c;
} else {
int m = l + r >> 1;
cover(l, m, a, b, c);
cover(m + 1, r, a, b, c);
maximum[id] = std::max(maximum[get_id(l, m)], maximum[get_id(m + 1, r)]) + delta[id];
}
}
int main()
{
int T;
scanf("%d", &T);
for (int t = 1; t <= T; ++ t) {
int m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++ i) {
tree[i].clear();
starts[i].clear();
}
for (int i = 0; i < n - 1; ++ i) {
int a, b;
scanf("%d%d", &a, &b);
a --;
b --;
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs_count = 0;
memset(same, 0, sizeof(*same) * n);
prepare(-1, 0);
for (int i = 0; i <= n; ++ i) {
events[i].clear();
}
for (int i = 0; i < m; ++ i) {
int from, to, weight;
scanf("%d%d%d", &from, &to, &weight);
from --;
to --;
if (from == to) {
same[from] += weight;
} else {
std::vector<Interval> begins = get_intervals(from, to);
std::vector<Interval> ends = get_intervals(to, from);
add_events(begins, ends, weight);
}
}
int total = 0;
for (int i = 0; i < n; ++ i) {
if (same[i]) {
total += same[i];
foreach (iterator, tree[i]) {
std::vector<Interval> intervals = get_intervals(*iterator, i);
add_events(intervals, intervals, -same[i]);
}
}
}
int result = INT_MIN;
memset(delta, 0, sizeof(*delta) * (n << 1));
memset(maximum, 0, sizeof(*maximum) * (n << 1));
for (int i = 0; i < n; ++ i) {
foreach (iterator, events[i]) {
cover(0, n - 1, iterator->y1, iterator->y2 - 1, iterator->w);
}
result = std::max(result, total + maximum[get_id(0, n - 1)]);
}
printf("Case #%d: %d\n", t, result);
}
}
Raw
H.cpp
#include <cassert>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <map>
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const int H = 10;
const int M = 4;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
typedef std::vector<int> State;
int w, part[1 << M];
std::map<int, int> transfer[1 << M][1 << M];
std::map<State, int> ways[2];
void update(int &x, int a)
{
x = std::min(x, a);
}
State go(const State& s, int board)
{
State ns(1 << w, INF);
for (int mask = 0; mask < 1 << w; ++ mask) {
foreach (iterator, transfer[mask][board]) {
update(ns[iterator->first], s[mask] + iterator->second);
}
}
return ns;
}
void add(int& x, int a)
{
x += a;
if (x >= MOD) {
x -= MOD;
}
}
std::map<int, int> result[M + 1][H + 1];
int main()
{
for (w = 1; w <= M; ++ w) {
for (int mask = 0; mask < 1 << w; ++ mask) {
part[mask] = 0;
for (int i = 0; i < w; ++ i) {
if ((mask >> i & 1) && (!i || (~mask >> i - 1 & 1))) {
part[mask] ++;
}
}
}
for (int from = 0; from < 1 << w; ++ from) {
for (int board = 0; board < 1 << w; ++ board) {
std::map<int, int>& T = transfer[from][board];
for (int tmp = 0; tmp < 1 << w; ++ tmp) {
int cost = part[board ^ tmp];
for (int i = 0; i < w && ~cost; ++ i) {
if ((from >> i & 1) && (~tmp >> i & 1)) {
cost = -1;
}
}
if (~cost) {
assert(cost >= 0);
for (int target = tmp; ; target = target - 1 & tmp) {
if (!T.count(target)) {
T[target] = INF;
}
T[target] = std::min(T[target], cost + __builtin_popcount(tmp ^ target));
if (!target) {
break;
}
}
}
}
}
}
State init_state(1 << w, INF);
ways[0].clear();
init_state[0] = 0;
ways[0][init_state] = 1;
for (int h = 1; h <= H; ++ h) {
//printf("ROW %d: \n", h);
ways[h & 1].clear();
foreach (iterator, ways[h + 1 & 1]) {
for (int board = 0; board < 1 << w; ++ board) {
add(ways[h & 1][go(iterator->first, board)], iterator->second);
}
}
foreach (iterator, ways[h & 1]) {
//printf("{%d,%d,%d,%d},",w,h,iterator->first[0],iterator->second);
add(result[w][h][iterator->first[0]], iterator->second);
//for (int mask = 0; mask < 1 << w; ++ mask) {
// for (int i = 0; i < w; ++ i) {
// printf("%d", mask >> i & 1);
// }
// printf(":%d,", iterator->first[mask]);
//}
//printf("%d\n", iterator->second);
}
// foreach (iterator, result[w][h]) {
// printf("{%d,%d,%d,%d},", w, h, iterator->first, iterator->second);
// }
}
}
int T;
scanf("%d", &T);
for (int t = 1; t <= T; ++ t) {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
int rr = 0;
foreach (iterator, result[n][m]) {
if (iterator->first <= k) {
add(rr, iterator->second);
}
}
printf("Case #%d: %d\n", t, rr);
}
}
Raw
I.cpp
#include <cstdio>
#include <queue>
#include <vector>
const int INF = 1000000000;
template<typename Type>
class Network
{
public:
Network(int n) : n(n), head(n, -1)
{
}
void add_edge(int u, int v, Type w)
{
add_edge_(u, v, w);
add_edge_(v, u, 0);
}
Type max_flow(int source, int target)
{
Type result = 0;
while (true) {
std::vector<int> level(n, -1);
level.at(target) = 0;
std::queue<int> queue;
queue.push(target);
while (!queue.empty() && !~level.at(source)) {
int v = queue.front();
queue.pop();
for (int iterator = head.at(v); ~iterator; ) {
Edge& edge = edges.at(iterator);
int u = edges.at(iterator).to;
if (edges.at(iterator ^ 1).capacity > 0 && !~level.at(u)) {
level.at(u) = level.at(v) + 1;
queue.push(u);
}
iterator = edge.next;
}
}
if (!~level.at(source)) {
break;
}
std::vector<int> current_head(head);
result += dfs(level, current_head, source, target, INF);
}
return result;
}
private:
struct Edge
{
Edge(int to, Type capacity, int next) : to(to), capacity(capacity), next(next) {}
int to;
Type capacity;
int next;
};
void add_edge_(int u, int v, Type w)
{
edges.push_back(Edge(v, w, head.at(u)));
head.at(u) = static_cast<int>(edges.size()) - 1;
}
Type dfs(const std::vector<int>& level, std::vector<int>& head, int u, int target, Type delta)
{
if (u == target) {
return delta;
}
Type left = delta;
for (int& iterator = head.at(u); ~iterator; ) {
Edge& edge = edges.at(iterator);
int v = edge.to;
if (edge.capacity > 0 && level.at(u) == level.at(v) + 1) {
Type ret = dfs(level, head, v, target, std::min(left, edge.capacity));
edge.capacity -= ret;
edges.at(iterator ^ 1).capacity += ret;
left -= ret;
if (!left) {
return delta;
}
}
iterator = edge.next;
}
return delta - left;
}
int n;
std::vector<int> head;
std::vector<Edge> edges;
};
const int N = 100;
int a[10], b[10], sum[N], w[N][N];
char buffer[N + 1];
int main()
{
int T;
scanf("%d", &T);
for (int t = 1; t <= T; ++ t) {
int n;
scanf("%d%s", &n, buffer);
for (int i = 0; i < 10; ++ i) {
scanf("%d%d", a + i, b + i);
}
int result = 0;
for (int i = 0; i < n; ++ i) {
sum[i] = 0;
for (int j = 0; j < n; ++ j) {
scanf("%d", w[i] + j);
sum[i] += w[i][j];
}
result += sum[i];
}
Network<int> network(n + 12);
int source = n + 10;
int target = n + 11;
for (int i = 0; i < 10; ++ i) {
network.add_edge(n + i, target, b[i] - a[i]);
}
for (int i = 0; i < n; ++ i) {
network.add_edge(source, i, sum[i]);
int c = buffer[i] - '0';
network.add_edge(i, target, a[c]);
network.add_edge(i, n + c, INF);
for (int j = 0; j < n; ++ j) {
if (i != j) {
network.add_edge(i, j, w[i][j]);
}
}
}
result -= network.max_flow(source, target);
printf("Case #%d: %d\n", t, result);
}
}
Raw
J.cpp
#include <algorithm>
#include <cstdio>
const int N = 100000;
int a[N], end[N + N + 1];
int main()
{
int T;
scanf("%d", &T);
for (int t = 1; t <= T; ++ t) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++ i) {
scanf("%d", a + i);
}
int result = 0;
int* p = end + n;
int delta = 0;
p[0] = -n;
for (int i = 0; i < n; ++ i) {
if (a[i]) {
int length = std::lower_bound(p, p + result + 1, a[i] - delta) - p;
if (length > result) {
result = length;
p[length] = a[i] - delta;
} else {
p[length] = std::min(p[length], a[i] - delta);
}
} else {
result ++;
delta ++;
p --;
p[0] = -n - delta;
}
}
printf("Case #%d: %d\n", t, result);
}
}
Raw
L.cpp
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<iomanip>
#include<complex>
#include<utility>
using namespace std;
int ans[100001];
int c[100001];
int N;
int T;
int a[100001];
inline void add(int x){
while(x<=N) ++c[x],x+=x&-x;
}
inline int sum(int x){
int ret=0;
while(x) ret+=c[x],x^=x&-x;
return ret;
}
int main(){
scanf("%d",&T);
for(int tt=1;tt<=T;++tt){
scanf("%d",&N);
for(int i=1;i<=N;++i){
scanf("%d",a+i);
c[i]=0;
}
for(int i=N;i>=1;--i){
int r=i+sum(a[i]);
add(a[i]);
ans[a[i]]=r-min(a[i],i);
}
printf("Case #%d:",tt);
for(int i=1;i<=N;++i) printf(" %d",ans[i]);
printf("\n");
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment