Submission #978414

#	Time	Username	Problem	Language	Result	Execution time	Memory
978414		hmm789	Koala Game (APIO17_koala)	C++14	100 / 100	56 ms	1136 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
 
int minValue(int N, int W) {
    int a[N], b[N];
    a[0] = 1;
    for(int i = 1; i < N; i++) a[i] = 0;
    playRound(a, b);
    for(int i = 0; i < N; i++) if(!b[i]) return i;
    return 0;
}
 
int maxValue(int N, int W) {
    int a[N], b[N];
    for(int i = 0; i < N; i++) a[i] = 1;
    playRound(a, b);
    set<int> s;
    for(int i = 0; i < N; i++) if(b[i]) s.insert(i);
    memset(a, 0, sizeof(a));
    for(int i : s) a[i] = 2;
    playRound(a, b);
    for(int i = 0; i < N; i++) if(s.find(i) != s.end() && !b[i]) s.erase(i);
    memset(a, 0, sizeof(a));
    for(int i : s) a[i] = 4;
    playRound(a, b);
    for(int i = 0; i < N; i++) if(s.find(i) != s.end() && !b[i]) s.erase(i);
    memset(a, 0, sizeof(a));
    for(int i : s) a[i] = 11;
    playRound(a, b);
    for(int i = 0; i < N; i++) if(s.find(i) != s.end() && !b[i]) s.erase(i);
    return *s.begin();
}
 
int greaterValue(int N, int W) {
    int a[N], b[N];
    memset(a, 0, sizeof(a));
    int l = 1, r = 9, m;
    while(l <= r) {
        m = (l+r)/2;
        a[0] = a[1] = m;
        playRound(a, b);
        if(b[0] && b[1]) l = m+1;
        else if(!b[0] && !b[1]) r = m-1;
        else if(b[0] && !b[1]) return 0;
        else return 1;
    }
    return 0;
}
 
int a[100], b[100], c[100], tmp[100];
bool cmp(int x, int y) {
    if(x == y) return false;
    a[x] = a[y] = 100;
    playRound(a, b);
    a[x] = a[y] = 0;
    return b[y] > 100;
}
 
void srt(int l, int r) {
    if(l == r) return;
    int m = (l+r)/2;
    srt(l, m);
    srt(m+1, r);
    int i = l, j = m+1, idx = l;
    while(i <= m || j <= r) {
        if(i > m) tmp[idx++] = c[j++];
        else if(j > r) tmp[idx++] = c[i++];
        else if(cmp(c[i], c[j])) tmp[idx++] = c[i++];
        else tmp[idx++] = c[j++];
    }
    for(int i = l; i <= r; i++) c[i] = tmp[i];
}
 
int ans[100];
 
void solve(int l, int r, int c, vector<int> pos) {
	//cout << l << " " << r << endl;
	if(l > r) return;
	if(pos.empty()) return;
	if(l == r) {
		//cout << l << " " << pos[0] << endl;
		ans[pos[0]] = l;
		return;
	}
	if(c == 0) c = min(100/(r-l+1), 8);
  	if(l == 1 && r <= 9) c = r-1;
  	if(l == 15 && r == 16) c = 6; // -2
	if(l == 17 && r == 19) c = 7; // -1
	if(l == 17 && r == 18) c = 6; // -2
	if(l == 20 && r == 21) c = 6; // -2
	memset(a, 0, sizeof(a));
	for(int i : pos) a[i] = c;
	playRound(a, b);
	
	//
	int B[100], R[100], P[100], N = 100, W = 100;
	for(int i = 0; i < 100; i++) P[i] = i+1;
	memset(B, 0, sizeof(B));
	for(int i = l-1; i < r; i++) B[i] = c;
	int cache[2][205];
    int num[2][205];
    char taken[105][205];
    for (int i=0;i<205;++i) {
        cache[1][i] = 0;
        num[1][i] = 0;
    }
    for (int i=0;i<N;++i) {
		//cout << "b " << i << endl;
        int v = B[i]+1;
        int ii = i&1;
        int o = ii^1;
        for (int j=0;j<=W;++j) {
            cache[ii][j] = cache[o][j];
            num[ii][j] = num[o][j];
            taken[i][j] = 0;
        }
        for (int j=W;j>=v;--j) {
            int h = cache[o][j-v] + P[i];
            int hn = num[o][j-v] + 1;
            if (h > cache[ii][j] || (h == cache[ii][j] && hn > num[ii][j])) {
                cache[ii][j] = h;
                num[ii][j] = hn;
                taken[i][j] = 1;
            } else {
                taken[i][j] = 0;
            }
        }
    }
    int cur = W;
    for (int i=N-1;i>=0;--i) {
        R[i] = taken[i][cur] ? (B[i] + 1) : 0;
        cur -= R[i];
    }
    //
    int m = r+1;
    for(int i = r-1; i >= l-1; i--) if(R[i] > B[i]) m = i+1;
    vector<int> v1, v2;
    for(int i : pos) {
		if(b[i] > a[i]) v2.push_back(i);
		else v1.push_back(i);
	}
	//cout << "a " << l << " " << m << " " << r << " " << c << endl;
	//for(int i : v1) cout << i << " ";
	//cout << endl;
	//for(int i : v2) cout << i << " ";
	//cout << endl;
	if(v2.size() == 0) {
		solve(l, m-1, c-1, v1);
	} else if(v1.size() == 0) {
		solve(m, r, c+1, v2);
	} else {
		solve(l, m-1, 0, v1);
		solve(m, r, 0, v2);
	}
}
 
void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        for(int i = 0; i < N; i++) c[i] = i;
        srt(0, N-1);
        for(int i = 0; i < N; i++) P[c[i]] = i+1;
    } else {
		vector<int> v;
		for(int i = 0; i < 100; i++) v.push_back(i);
        solve(1, 100, 0, v);
        for(int i = 0; i < 100; i++) P[i] = ans[i];
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 53 / 53