| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 380318 | rainboy | Land of the Rainbow Gold (APIO17_rainbow) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "koala.h"
#include <stdio.h>
#include <string.h>
#define N 100
int minValue(int n, int w) {
static int bb[N], rr[N];
int i;
memset(bb, 0, n * sizeof *bb), bb[0] = 1;
playRound(bb, rr);
for (i = 1; i < n; i++)
if (rr[i] == 0)
return i;
return 0;
}
int aa[] = { 2, 4, 11 };
char used[N];
int maxValue(int n, int w) {
static int bb[N], rr[N];
int i, r;
for (i = 0; i < N; i++)
bb[i] = 1;
playRound(bb, rr);
for (r = 0; r < 3; r++) {
for (i = 0; i < N; i++)
if (bb[i] && rr[i] > bb[i])
bb[i] = aa[r];
else
bb[i] = 0;
playRound(bb, rr);
}
for (i = 0; i < N; i++)
if (bb[i] && rr[i] > bb[i])
return i;
return -1;
}
int greaterValue(int n, int w) {
/*
static int bb[N], rr[N];
int i_ = maxValue(n, w), i;
if (i_ < 2)
return i_;
for (i = 0; i < n; i++)
bb[i] = 1;
bb[i_] = bb[0] = bb[1] = 0;
playRound(bb, rr);
return rr[0] > bb[0];
*/
return n + w;
}
int n_;
int compare(int i, int j) {
static int bb[N], rr[N];
memset(bb, 0, n_ * sizeof *bb);
bb[i] = bb[j] = n_;
playRound(bb, rr);
return rr[i] > bb[i] ? 1 : -1;
}
void sort(int *ii, int l, int r) {
static int jj[N];
int m, i, j, k;
if (r - l == 1)
return;
m = (l + r) / 2;
sort(ii, l, m), sort(ii, m, r);
i = l, j = m, k = l;
while (i < m && j < r)
jj[k++] = compare(ii[i], ii[j]) < 0 ? ii[i++] : ii[j++];
while (i < m)
jj[k++] = ii[i++];
while (j < r)
jj[k++] = ii[j++];
memcpy(ii + l, jj + l, (r - l) * sizeof *jj);
}
int lrb[][3] = {
{ 0, 100, 1 }, { 0, 50, 1 }, { 0, 50, 2 }, { 50, 100, 1 }, { 50, 100, 2 },
{ 0, 25, 1 }, { 0, 25, 2 }, { 0, 25, 3 }, { 0, 25, 4 }, { 25, 34, 2 },
{ 25, 34, 3 }, { 25, 34, 4 }, { 25, 34, 5 }, { 25, 34, 8 }, { 34, 50, 2 },
{ 34, 50, 3 }, { 34, 50, 4 }, { 34, 50, 5 }, { 34, 50, 6 }, { 50, 60, 2 },
{ 50, 60, 3 }, { 50, 60, 4 }, { 50, 60, 5 }, { 50, 60, 7 }, { 50, 60, 10 },
{ 60, 75, 2 }, { 60, 75, 3 }, { 60, 75, 4 }, { 60, 75, 5 }, { 75, 100, 2 },
{ 75, 100, 3 }, { 75, 100, 4 }, { 0, 13, 1 }, { 0, 13, 2 }, { 0, 13, 3 },
{ 0, 13, 4 }, { 0, 13, 6 }, { 13, 17, 2 }, { 13, 17, 3 }, { 13, 17, 4 },
{ 17, 19, 3 }, { 20, 25, 2 }, { 20, 25, 3 }, { 20, 25, 4 }, { 20, 25, 5 },
{ 25, 28, 3 }, { 25, 28, 5 }, { 28, 30, 4 }, { 34, 40, 3 }, { 34, 40, 4 },
{ 34, 40, 5 }, { 34, 40, 7 }, { 40, 43, 4 }, { 40, 43, 6 }, { 43, 45, 5 },
{ 47, 50, 4 }, { 47, 50, 6 }, { 51, 54, 5 }, { 51, 54, 6 }, { 54, 56, 6 },
{ 60, 63, 5 }, { 60, 63, 7 }, { 63, 67, 4 }, { 63, 67, 5 }, { 63, 67, 7 },
{ 67, 69, 7 }, { 69, 71, 7 }, { 71, 75, 5 }, { 71, 75, 6 }, { 71, 75, 8 },
{ 75, 83, 3 }, { 75, 83, 4 }, { 75, 83, 5 }, { 75, 83, 7 }, { 75, 83, 10 },
{ 83, 88, 4 }, { 83, 88, 5 }, { 83, 88, 6 }, { 83, 88, 9 }, { 88, 91, 6 },
{ 88, 91, 8 }, { 91, 100, 3 }, { 91, 100, 4 }, { 91, 100, 5 }, { 91, 100, 6 },
{ 91, 100, 8 }, { 91, 100, 11 }, { 0, 7, 1 }, { 0, 7, 2 }, { 0, 7, 3 },
{ 7, 9, 2 }, { 34, 36, 5 }, { 76, 78, 7 }, { 78, 80, 7 }, { 92, 95, 6 },
{ 92, 95, 8 }, { 0, 4, 1 }, { 0, 4, 2 }, { 0, 2, 1 },
}; /* done by hand */
void allValues(int n, int w, int *pp) {
static int ii[N];
int i;
for (i = 0; i < n; i++)
ii[i] = i;
if (w == n * 2) /* mergesort */
n_ = n, sort(ii, 0, n);
else { /* quicksort */
static int bb[N], rr[N];
int h;
for (h = 0; h < 99; h++) {
int l = lrb[h][0], r = lrb[h][1], b = lrb[h][2], tmp;
memset(bb, 0, n * sizeof *bb);
for (i = l; i < r; i++)
bb[ii[i]] = b;
playRound(bb, rr);
while (l < r)
if (rr[ii[l]] <= bb[ii[l]])
l++;
else {
r--;
tmp = ii[l], ii[l] = ii[r], ii[r] = tmp;
}
}
}
for (i = 0; i < n; i++)
pp[ii[i]] = i + 1;
}