The official APIO 2017 Problems and solutions in this post.
Problem – A (Koala Game) :
enSolution – A (Koala Game) :
#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
#define FO(i,a,b) for (int i = (a); i < (b); i++)
#define pb push_back
#define sz(v) ((int)v.size())
struct Query {
vector <int> am;
};
struct Response {
vector <bool> v;
};
int N, W;
Response makeQuery (Query q) {
int *B = (int *)malloc(sizeof(int)*N);
FO (i,0,N) B[i] = q.am[i];
int *R = (int *)malloc(sizeof(int)*N);
playRound(B,R);
Response r;
FO (i,0,N) {
if (R[i] > B[i]) {
r.v.pb(true);
} else {
r.v.pb(false);
}
}
free(B);
free(R);
return r;
}
Response makeUniformQuery (set<int> &cand, int am) {
Query q;
FO (i,0,N) {
if (cand.find(i) != cand.end()) {
q.am.pb(am);
} else {
q.am.pb(0);
}
}
return makeQuery(q);
}
set<int> responseToSet (Response r) {
set <int> s;
FO (i,0,N) if (r.v[i]) s.insert(i);
return s;
}
int minValue(int _N, int _W) {
N = _N; W = _W;
set <int> cand;
cand.insert(0);
Response r = makeUniformQuery(cand, 1);
FO (i,0,N) {
if (!r.v[i]) return i;
}
assert (false);
}
int actualGetMax() {
set <int> cand;
FO (i,0,N) cand.insert(i);
while (cand.size() > 1) {
Response r = makeUniformQuery(cand, W/(int)cand.size());
set <int> newC;
FO (i,0,N) if (cand.find(i) != cand.end() && r.v[i]) newC.insert(i);
cand = newC;
}
return *(cand.begin());
}
int maxValue(int _N, int _W) {
N = _N; W = _W;
return actualGetMax();
}
int greaterValue(int _N, int _W) {
N = _N; W = _W;
set <int> f2 = {0,1};
int cands[4] = {1,3,6,8};
int lo = 0;
int hi = 3;
int mid;
while (lo <= hi) {
mid = (lo+hi)/2;
Response r = makeUniformQuery(f2, cands[mid]);
set <int> origRes = responseToSet(r);
set <int> res;
for (auto c : f2) {
if (origRes.find(c) != origRes.end()) res.insert(c);
}
switch (res.size()) {
case 0:
hi = mid-1;
break;
case 1:
return *(res.begin());
case 2:
lo = mid+1;
break;
}
}
assert(false);
}
vector <int> sortRange (vector <int> vals);
void solveMain(int *P);
void allValues(int _N, int _W, int *P) {
N = _N; W = _W;
if (_W == 2*_N) {
vector <int> startVals;
FO (i,0,N) startVals.pb(i);
vector <int> endVals = sortRange(startVals);
FO (i,0,N) P[endVals[i]] = N-i;
} else {
solveMain(P);
}
}
// returns greater of the 2
int sub4cmp(int a, int b) {
set<int> vals = {a,b};
set<int> takens = responseToSet(makeUniformQuery(vals, W/2));
if (takens.find(a) != takens.end()) return a;
else return b;
}
vector <int> sortRange (vector <int> vals) {
if (vals.size() == 1) return vals;
vector <int> fV, sV;
FO (i,0,sz(vals)) {
if (i%2) sV.pb(vals[i]);
else fV.pb(vals[i]);
}
vector <int> sF = sortRange(fV);
vector <int> sS = sortRange(sV);
int fI(0), sI(0);
vector <int> retV;
while (fI < sz(sF) || sI < sz(sS)) {
if (fI == sz(sF)) retV.pb(sS[sI++]);
else if (sI == sz(sS)) retV.pb(sF[fI++]);
else {
if (sub4cmp(sF[fI], sS[sI]) == sF[fI]) {
retV.pb(sF[fI++]);
} else {
retV.pb(sS[sI++]);
}
}
}
return retV;
}
set <int> lowestVals;
#define N_BUCKETS 9
#define B_SIZ 10
vector <int> startBuckets[N_BUCKETS];
vector <int> sortedB[N_BUCKETS];
int valToPos[105];
int maxInSet(set<int> &s) {
// Need this:
assert(s.size() <= 9);
set<int> qSet(s);
for (int i = 10; i >= 1; i--) {
if (qSet.size() == 9) break;
qSet.insert(valToPos[i]);
}
set<int> taken;
if (s.size() == 1) {
taken = responseToSet(makeUniformQuery(qSet, 10));
} else {
taken = responseToSet(makeUniformQuery(qSet, 11));
}
for (int v : s) {
if (taken.find(v) != taken.end()) return v;
}
assert(false);
}
void solveMain (int *P) {
lowestVals.clear();
FO (i,0,N_BUCKETS) {
startBuckets[i].clear();
sortedB[i].clear();
}
int mx = actualGetMax();
set<int> mxSet({mx});
set<int> notLowestVals =
responseToSet(makeUniformQuery(mxSet, 10));
FO (i,0,N) {
if (notLowestVals.count(i) == 0) lowestVals.insert(i);
}
assert(lowestVals.size() == 10);
FO (i,0,N) {
if (lowestVals.find(i) != lowestVals.end()) continue;
FO (b,0,N_BUCKETS) {
if (startBuckets[b].size() < B_SIZ) {
startBuckets[b].pb(i);
break;
}
}
}
// Get bottom 10:
set <int> lowLeft (lowestVals);
while (lowLeft.size()) {
if (lowLeft.size() == 1) {
valToPos[1] = *lowLeft.begin();
break;
}
set <int> res =
responseToSet(makeUniformQuery(lowLeft, lowLeft.size()-1));
for (int v : res) {
if (lowLeft.find(v) != lowLeft.end()) {
valToPos[lowLeft.size()] = v;
lowLeft.erase(v);
break;
}
}
}
FO (b,0,N_BUCKETS) {
set <int> remThings(startBuckets[b].begin(), startBuckets[b].end());
while (remThings.size()) {
if (remThings.size() == 10) {
// one special case:
set <int> res = responseToSet(makeUniformQuery(remThings, 10));
set <int> cMax;
for (int v : res) {
if (remThings.find(v) != remThings.end()) {
cMax.insert(v);
}
}
if (cMax.size() == 2) {
int mx = maxInSet(cMax);
sortedB[b].pb(mx);
cMax.erase(mx);
sortedB[b].pb(*cMax.begin());
remThings.erase(mx);
remThings.erase(*cMax.begin());
} else if (cMax.size() == 1) {
sortedB[b].pb(*cMax.begin());
remThings.erase(*cMax.begin());
} else {
assert(false);
}
} else {
int mx;
if (remThings.size() == 1) mx = *remThings.begin();
else mx = maxInSet(remThings);
sortedB[b].pb(mx);
remThings.erase(mx);
}
}
}
// Merge buckets:
// Sort buckets into increasing order not decreasing:
FO (i,0,N_BUCKETS) reverse(sortedB[i].begin(), sortedB[i].end());
vector <int> sortedAll;
while(true) {
set <int> cFronts;
FO (i,0,N_BUCKETS) {
if (sortedB[i].size()) {
cFronts.insert(sortedB[i].back());
}
}
if (cFronts.empty()) break;
int mx = maxInSet(cFronts);
sortedAll.pb(mx);
FO (i,0,N_BUCKETS) {
if (sortedB[i].size() && sortedB[i].back() == mx) {
sortedB[i].pop_back();
}
}
}
for (int i = 10; i >= 1; i--) {
sortedAll.pb(valToPos[i]);
}
FO (i,0,sz(sortedAll)) {
P[sortedAll[i]] = N-i;
}
}Problem – B (Merchant) :
en-1Solution – B (Merchant) :
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<lint, lint> pi;
int n, m, k;
int b[105][1005], s[105][1005];
int adj[105][105], dx[105][105];
llf gph[105][105];
bool trial(llf t){
// TotalProfit - t * TotalTime > 0
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(adj[i][j] > 1e9 + 10) gph[i][j] = -1e12;
else gph[i][j] = dx[i][j] - t * adj[i][j];
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
for(int k=1; k<=n; k++){
gph[j][k] = max(gph[j][k], gph[j][i] + gph[i][k]);
}
}
}
for(int i=1; i<=n; i++){
if(gph[i][i] >= 0) return 1;
}
return 0;
}
int main(){
scanf("%d %d %d",&n,&m,&k);
for(int i=1; i<=n; i++){
for(int j=0; j<k; j++) scanf("%d %d",&b[i][j],&s[i][j]);
}
memset(adj, 0x3f, sizeof(adj));
for(int i=0; i<m; i++){
int s, e, x;
scanf("%d %d %d",&s,&e,&x);
adj[s][e] = x;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
for(int k=1; k<=n; k++){
adj[j][k] = min(adj[j][i] + adj[i][k], adj[j][k]);
}
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
for(int l=0; l<k; l++){
if(~s[j][l] && ~b[i][l]) dx[i][j] = max(dx[i][j], s[j][l] - b[i][l]);
}
}
}
llf s = 0, e = 2e9;
for(int i=0; i<100; i++){
llf m = (s+e)/2;
if(trial(m)) s = m;
else e = m;
}
printf("%lld",(lint)floor(e));
}
Problem – C (Land of the Rainbow Gold) :
en-2Solution – C (Land of the Rainbow Gold) :
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
const int MAXT = 20000000;
const int MAXN = 200005;
struct node{
int l, r, sum;
}pool[MAXT];
int piv;
int newnode(){ return ++piv; }
void init(int s, int e, int p){
if(s == e) return;
int m = (s+e)/2;
pool[p].l = newnode();
pool[p].r = newnode();
init(s, m, pool[p].l);
init(m+1, e, pool[p].r);
}
void add(int pos, int s, int e, int prv, int cur){
pool[cur].sum = pool[prv].sum + 1;
if(s == e) return;
int m = (s+e)/2;
if(pos <= m){
pool[cur].l = newnode();
pool[cur].r = pool[prv].r;
add(pos, s, m, pool[prv].l, pool[cur].l);
}
else{
pool[cur].l = pool[prv].l;
pool[cur].r = newnode();
add(pos, m+1, e, pool[prv].r, pool[cur].r);
}
}
int query(int s, int e, int ps, int pe, int p){
if(e < ps || pe < s) return 0;
if(s <= ps && pe <= e) return pool[p].sum;
int pm = (ps + pe) / 2;
return query(s, e, ps, pm, pool[p].l) + query(s, e, pm+1, pe, pool[p].r);
}
int tree[4][MAXN];
vector<int> v[4][MAXN];
int minx = 1e9, miny = 1e9, maxx = -1e9, maxy = -1e9, yMax;
void init(int R, int C, int sr, int sc, int M, char *S) {
auto upload = [&](int x, int y){
v[0][x].push_back(y);
v[0][x].push_back(y + 1);
v[0][x + 1].push_back(y);
v[0][x + 1].push_back(y + 1);
v[1][x].push_back(y);
v[1][x].push_back(y + 1);
v[2][x].push_back(y);
v[2][x + 1].push_back(y);
v[3][x].push_back(y);
minx = min(minx, x); maxx = max(maxx, x + 1);
miny = min(miny, y); maxy = max(maxy, y + 1);
};
upload(sr, sc);
for(int i=0; i<M; i++){
if(S[i] == 'N') sr--;
if(S[i] == 'S') sr++;
if(S[i] == 'E') sc++;
if(S[i] == 'W') sc--;
upload(sr, sc);
}
yMax = C + 1;
for(int i=0; i<4; i++){
tree[i][0] = newnode();
init(1, yMax, tree[i][0]);
for(int j=1; j<=R+1; j++){
sort(v[i][j].begin(), v[i][j].end());
v[i][j].resize(unique(v[i][j].begin(), v[i][j].end()) - v[i][j].begin());
int prv = tree[i][j-1];
for(auto &k : v[i][j]){
int nxt = newnode();
add(k, 1, yMax, prv, nxt);
prv = nxt;
}
tree[i][j] = prv;
}
}
}
int colour(int ar, int ac, int br, int bc) {
auto query_helper = [&](int idx, int sx, int ex, int sy, int ey){
return query(sy, ey, 1, yMax, tree[idx][ex])
- query(sy, ey, 1, yMax, tree[idx][sx - 1]);
};
int V = query_helper(0, ar + 1, br, ac + 1, bc);
int E = query_helper(1, ar, br, ac + 1, bc) + query_helper(2, ar + 1, br, ac, bc);
int F = query_helper(3, ar, br, ac, bc);
if(ar < minx && maxx < br + 1 && ac < miny && maxy < bc + 1){
return 2 + E - V - F;
}
return 1 + E - V - F;
}500 total views, 1 views today