Codeforces Round #498 (Div. 3)

Codeforces Round #498 (Div. 3) : http://codeforces.com/contest/1006

A.

#include <stdio.h>
 
int main()
{
    int n, k;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++) {
        scanf("%d", &k);
        if(k%2 == 0) k--;
        printf("%d ", k);
    }
    puts("");
    return 0;
}
 

B. 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
struct P { int i, d; };
 
bool cmp(P a, P b)
{
    return a.d > b.d;
}
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
 
    vector<P> v;
    for(int i=0; i<n; i++) {
        int a;
        scanf("%d", &a);
        v.push_back((P){i, a});
    }
    
    sort(v.begin(), v.end(), cmp);
    
    int sum=0;
    vector<int> ans;
    for(int i=0; i<k; i++) {
        sum += v[i].d;
        ans.push_back(v[i].i);
    }
    
    sort(ans.begin(), ans.end());
    ans[ans.size()-1] = n-1;
 
    printf("%d\n", sum);
    
    printf("%d ", ans[0]+1);
    for(int i=1; i<ans.size(); i++)
        printf("%d ", ans[i]-ans[i-1]);
    puts("");
    return 0; 
}
 
 

C.

#include <cstdio>
 
typedef long long int lli;
 
int a[200005];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++) 
        scanf("%d", a+i);
 
    int s=0, e=n-1;
    lli sSum=a[s], eSum=a[e];
    int sIdx=-1, eIdx=-1;
 
    while(s < e) {
        if(sSum == eSum) {
            sIdx = s; eIdx = e;
        }
        if(sSum <= eSum) {
            sSum += a[++s];
        }
        else
            eSum += a[--e];
    }
 
    lli ans=0LL;
    if(sIdx != -1) {
        for(int i=0; i<=sIdx; i++)
            ans += a[i];
    }
    printf("%lld\n", ans);
    return 0;
}
 
 

>> Two Pointers

D.

E. 

#include <cstdio>
#include <vector>
using namespace std;
 
int cnt[200005];
vector<int> g[200005];
 
vector<int> order;
int oIdx[200005];
 
int dfs(int s)
{
    int ret=1;
    oIdx[s] = order.size();
    order.push_back(s);
 
    for(int i=0; i<g[s].size(); i++) {
        int next = g[s][i];
        cnt[next] = dfs(next);
        ret += cnt[next];
    }
    return ret;
}
 
int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
 
    for(int i=2; i<=n; i++) {
        int p;
        scanf("%d", &p);
        g[p].push_back(i);
    }
 
    cnt[1] = dfs(1);
 
    while(q--) {
        int u, k;
        scanf("%d%d", &u, &k);
        if(cnt[u] < k) puts("-1");
        else printf("%d\n", order[oIdx[u]+k-1]);
    }
    return 0;
}
 
 

>> DFS order

F.

#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
 
typedef long long int lli;
 
int n, m, half;
lli k, ans;
lli g[21][21];
 
map<lli, int> d[21][21];
 
void goHalf(int r, int c, lli xr, int cnt)
{
    xr = xr^g[r][c];
    if(cnt == half) {
        d[r][c][xr]++;
        return ;
    }
    
    if(r+1 < n) goHalf(r+1, c, xr, cnt+1);
    if(c+1 < m) goHalf(r, c+1, xr, cnt+1); 
}
 
void goEnd(int r, int c, lli xr, int cnt)
{
    if(cnt == (n+m-2-half)) {
        ans += d[r][c][xr^k]; // a^b^b = k^b = a
        return ;
    }
 
    if(r-1 >= 0) goEnd(r-1, c, xr^g[r][c], cnt+1);
    if(c-1 >= 0) goEnd(r, c-1, xr^g[r][c], cnt+1);
}
 
int main()
{
    scanf("%d%d%lld", &n, &m, &k);
 
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            scanf("%lld", &g[i][j]);
 
    half = (n+m-2)/2;
    goHalf(0, 0, 0, 0);
    goEnd(n-1, m-1, 0, 0);
   
    printf("%lld\n", ans);
    return 0;
}
 

>> Meet in the Middle