Submission #263590

#	Time	Username	Problem	Language	Result	Execution time	Memory
263590		keko37	Minerals (JOI19_minerals)	C++14	100 / 100	75 ms	4252 KiB

minerals

#include<bits/stdc++.h>
#include "minerals.h"

using namespace std;

typedef vector <int> vi;

const int MAXN = 45000;

int n, prosli = 0;
int dp[MAXN], opt[MAXN];

int calc (int len) {
    if (dp[len] != -1) return dp[len];
    if (len == 1) return dp[len] = 0;
    int res = 1e9;
    int x = (double) len / 2.618;
    for (int j = 0; j <= 1; j++) {
        int i = x + j;
        if (i < 1 || i >= len) continue;
        int tmp = min(i, len - i) + len - 1 + calc(i) + calc(len - i);
        if (tmp < res) {
            res = tmp;
            opt[len] = i;
        }
    }
    return dp[len] = res;
}

bool pitaj (int x) {
	int novi = Query(x);
	bool res = (prosli != novi);
	prosli = novi;
	return res;
}

void calc (vi a, vi b, bool flg) {
	int siz = a.size();
	if (siz == 1) {
		Answer(a[0], b[0]);
		return;
	}
	int x = opt[siz];
	vi a1, b1, a2, b2;
	for (int i = 0; i < siz; i++) {
		if (i < x) {
			pitaj(a[i]);
			a1.push_back(a[i]);
		} else {
			a2.push_back(a[i]);
		}
	}
	for (int i = 0; i < siz; i++) {
		if (b1.size() == a1.size()) {b2.push_back(b[i]); continue;}
		if (b2.size() == a2.size()) {b1.push_back(b[i]); continue;}
		if (pitaj(b[i]) ^ flg) b2.push_back(b[i]); else b1.push_back(b[i]);
	}
	calc(a1, b1, !flg);
	calc(a2, b2, flg);
}

void init () {
	vi a, b;
	for (int i = 1; i <= 2 * n; i++) {
		if (pitaj(i)) a.push_back(i); else b.push_back(i);
	}
	calc(a, b, 1);
}

void Solve (int N) {
	n = N;
	memset(dp, -1, sizeof dp);
	calc(n);
	init();
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10