＃１１２（Div.2)

とりあえず一完しかできなかった、悲しみ

A

やるだけ

#include <cstdio>
int x[200], y[200];
int ri[200], le[200], lo[200], up[200];
int main() {
    int n;
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d%d",&x[i],&y[i]);
    }
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if (x[i]>x[j]&&y[i]==y[j]) {
                le[i]++; ri[j]++;
            } else if (x[i]<x[j]&&y[i]==y[j]) {
                le[j]++; ri[i]++;
            } else if (y[i]>y[j]&&x[i]==x[j]) {
                lo[i]++; up[j]++;
            } else if (y[i]<y[j]&&x[i]==x[j]) {
                lo[j]++; up[i]++;
            }
        }
    }
    int res=0;
    for (int i=0; i<n; i++) if (le[i]&&ri[i]&&lo[i]&&up[i]) res++;
    printf("%d\n",res);
}

B

二分探索の上限値をミスってどぼんしました
追記：実験の結果上限値は関係ありませんでしたorz

#include <cstdio>
#include <cmath>
int n, k;
bool C(int v) {
    int sum=0;
    int x=1;
    while (floor(v/x)!=0) {
        sum+=floor(v/x);
        x*=k;
    }
//    printf("%d %d\n",v,sum);
    if (sum>=n) return true;
    else return false;
}
int main() {
    scanf("%d%d",&n,&k);
    int l=0, r=n+1;
    while (r-l>1) {
        int mid=(l+r)/2;
        if (C(mid)) {
            r=mid;
        } else {
            l=mid;
        }
    }
    printf("%d\n",r);
}

通るのは下

#include <cstdio>
#include <cmath>
int n, k;
bool C(int v) {
    int sum=0;
    while (v!=0) {
        sum+=v;
        v/=k;
    }
//    printf("%d %d\n",v,sum);
    if (sum>=n) return true;
    else return false;
}
int main() {
    scanf("%d%d",&n,&k);
    int l=0, r=n+1;
    while (r>l) {
        int mid=(l+r)/2;
        if (C(mid)) {
            r=mid;
        } else {
            l=mid+1;
        }
    }
    printf("%d\n",l);
}

C

しゃくとりとかなんとか
実装難しくて放棄してしまった

D

本当はLCA問題
・・・が、Div.2の人でLCA知らない人がDijkstraで書いてプレテストだけとおして自己満できるようにつくられてる
まぁDijkstraはO(nm log n)だから当然TLEです

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <functional>
#define inf 10000000
using namespace std;
typedef pair<int, int> P;
struct edge {
    int from, to, cost;
    bool flag;
};
int n, m;
edge es[100000];
vector<edge*> G[100000];
int d[100000];
int dijkstra(int a, int b) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+n, inf);
    d[a]=0;
    que.push(P(0,a));
    while (!que.empty()) {
        P p=que.top(); que.pop();
        int v=p.second;
        if (d[v]<p.first) continue;
        for (int i=0; i<G[v].size(); i++) {
            edge e=*G[v][i];
            if (e.to==v) swap(e.to, e.from);
            if (d[e.to]>d[v]+e.cost&&e.flag) {
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
    if (d[b]==inf) return -1;
    else return d[b];
}
int main() {
    scanf("%d",&n);
    for (int i=0; i<n-1; i++) {
        int v, u; scanf("%d%d",&v,&u);
        es[i]=(edge){v-1,u-1,1,true};
        G[v-1].push_back(&es[i]);
        G[u-1].push_back(&es[i]);
    }
    scanf("%d",&m);
    for (int i=0; i<m; i++) {
        int t; scanf("%d",&t);
        if (t==1) {
            int id; scanf("%d",&id);
            es[id-1].flag=true;
        } else if (t==2) {
            int id; scanf("%d",&id);
            es[id-1].flag=false;
        } else if (t==3) {
            int a, b; scanf("%d%d",&a,&b);
            printf("%d\n",dijkstra(a-1,b-1));
        }
    }
}

E

とりあえず単純解法のO(n^2)を投げて当然のごとくTLE
正答は、なんかbitを一個ひっくり返してほにゃららで前計算して、xorで求めるようです。知らない。

#include <cstdio>
int ans[1000005];
int a[1000005];
int main() {
    int n; scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
        ans[i]=-1;
    }
    for (int i=0; i<n; i++) {
        if (ans[i]==-1) {
            for (int j=0; j<n; j++) if (i!=j&&(a[i]&a[j])==0) {
                ans[i]=a[j];
                ans[j]=a[i];
                break;
            }
        }
    }
    for (int i=0; i<n; i++) {
        printf("%d%c",ans[i],i==n-1?'\n':' ');
    }
}