| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 404092 |
2021-05-13T18:34:49 Z |
yoavL |
Koala Game (APIO17_koala) |
C++14 |
|
100 ms |
328 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <fstream>
#include <iomanip>
#include "koala.h"
using namespace std;
using ll = int;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vld = vector<ld>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using pb = pair<bool, bool>;
using vpb = vector<pb>;
using vvpb = vector<vpb>;
using vi = vector<int>;
using vvi = vector<vi>;
const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e18;
#define F first
#define S second
#define FAST ios_base::sync_with_stdio(0)
#define FASTIN cin.tie(0)
#define FASTOUT cout.tie(0)
#define upmin(a, b) a = min(a, b)
#define upmax(a, b) a = max(a, b)
#define whatvec(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define prv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define wpr(x) cout << #x << " = " << (x) << endl;
#define wprv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define what(x) cout << #x << " = " << (x) << "\n";
#define pr(x) cout <<x << endl;
#define rep(i,s,e) for(ll i = s;i < e; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
const ll len = 100;
const ll maxcap = 8;
ll a[len], b[len];
ll qnum;
void fill(ll ind)
{
for (ll i = 0; i < len; i++) a[i] = 0;
a[ind] = 1;
}
void pra()
{
pr("a:");
rep(i, 0, len) {
cout << a[i] << " ";
}
cout << endl;
}
void prb()
{
pr("b:");
rep(i, 0, len) {
cout << b[i] << " ";
}
cout << endl;
}
int minValue(int N, int W) {
//pr("here");
// TODO: Implement Subtask 1 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
ll n = N, w = W;
//vll a(n, 1);
fill(0);
rep(i, 0, len) b[i] = -1;
bool ok = false;
playRound(a, b);
rep(i, 0, len) if (b[i] != -1) ok = true;
if (!ok) while (true);
for (ll i = 0; i < len; i++) {
if (b[i] == 0) return i;
}
fill(1);
playRound(a, b);
rep(i, 0, len) {
if (b[i] == 0) return i;
}
while (true);
return 0;
}
int rec(vll ind)
{
if (ind.size() == 1) {
return ind[0];
}
ll sz = ind.size();
ll cap = len / sz;
rep(i, 0, len) {
a[i] = 0;
}
rep(i, 0, sz) {
a[ind[i]] = cap;
}
/*
pr("a:");
rep(i, 0, len) {
cout << a[i] << " ";
}
cout << endl;
*/
playRound(a, b);
/*
pr("b:");
rep(i, 0, len) {
cout << b[i] << " ";
}
cout << endl;
*/
ll maxv = 0;
rep(i, 0, len) {
upmax(maxv, b[i]);
}
vll nind;
rep(i, 0, len) {
if (b[i] == maxv) nind.push_back(i);
}
return rec(nind);
}
int maxValue(int N, int W) {
// TODO: Implement Subtask 2 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
vll ind;
for (ll i = 0; i < len; i++) ind.push_back(i);
return rec(ind);
}
int put_v_comp(ll v, ll i1, ll i2)
{
if ((i1 < 0) || (i2 < 0) || (i1 >= len) || (i2 >= len) || (i1 == i2)) while (true);
//wpr(v);
rep(i, 0, len) {
a[i] = 0;
}
a[i1] = a[i2] = v;
//pra();
qnum++;
//if (qnum > 2200) while (true);
playRound(a, b);
//prb();
if (b[i1] > b[i2]) return 0;
if (b[i1] < b[i2]) return 1;
if (b[i1] > 0) return 2;
return 3;
}
bool comp(ll i, ll j)
{
if (i == j) return false;
//cout << "comp: " << i << ", " << j << endl;
ll low = 0, high = maxcap, mid = 0;
while (low <= high) {
mid = (low + high) / 2;
ll res = put_v_comp(mid, i, j);
//wpr(res);
if (res <= 1) {
return res;
}
if (res == 2) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
/*
for (ll mid = 0; mid <= maxcap; mid++) {
ll res = put_v_comp(mid, i, j);
//wpr(res);
if (res <= 1) {
return res;
}
if (res == 2) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
*/
while (true);
return false;
}
bool comp2(ll a, ll b)
{
ll tans = put_v_comp(100, a, b);
if (tans > 1) while (true);
return tans;
}
int greaterValue(int N, int W) {
// TODO: Implement Subtask 3 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
return comp(0, 1);
}
void allValues(int N, int W, int* P) {
qnum = 0;
vll inds(len);
for (ll i = 0; i < len; i++) {
inds[i] = i;
}
//pr("wasup");
if (W == 2 * N) {
// TODO: Implement Subtask 4 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
sort(inds.begin(), inds.end(), comp2);
}
else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
sort(inds.begin(), inds.end(), comp);
rep(i, 1, len) {
if (comp(inds[i], inds[i - 1])) while (true);
}
}
rep(i, 0, len)
{
P[i] = inds[i] + 1;
if ((P[i] <= 0) || (P[i] > len)) while (true);
}
}
/*
4 1
6 12
5 3 2 1 6 4
3 1
6 6
5 3 2 1 6 4
3 1
6 6
3 5 2 1 6 4
4 1
6 6
5 3 2 1 6 4
4 1
6 6
5 3 2 1 6 4
3 1
6 6
1 2 5 3 6 4
3 1
6 6
5 4 3 2 1
4 1
6 6
5 3 2 1 6 4
5 1
6 6
1 2 5 3 6 4
4 1
6 6
1 2 3 4 5 6
4 1
100 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
4 1
100 100
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66
65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
4 1
100 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
39 40 41 42 43 44 45 46 47 48 49 50
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66
65 64 63 62 61 60 59 58 57 56 55 54 53 52 51
4 1
6 6
5 3 2 1 6 4
4 1
100 200
100 1 99 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 98 97
*/
Compilation message
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:104:8: warning: unused variable 'n' [-Wunused-variable]
104 | ll n = N, w = W;
| ^
koala.cpp:104:15: warning: unused variable 'w' [-Wunused-variable]
104 | ll n = N, w = W;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
200 KB |
Output is correct |
| 2 |
Correct |
5 ms |
200 KB |
Output is correct |
| 3 |
Correct |
5 ms |
200 KB |
Output is correct |
| 4 |
Correct |
5 ms |
200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
200 KB |
Output is correct |
| 2 |
Correct |
18 ms |
200 KB |
Output is correct |
| 3 |
Correct |
15 ms |
200 KB |
Output is correct |
| 4 |
Correct |
15 ms |
312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
76 ms |
316 KB |
Output is partially correct |
| 2 |
Partially correct |
100 ms |
320 KB |
Output is partially correct |
| 3 |
Partially correct |
80 ms |
320 KB |
Output is partially correct |
| 4 |
Partially correct |
70 ms |
320 KB |
Output is partially correct |
| 5 |
Partially correct |
70 ms |
320 KB |
Output is partially correct |
| 6 |
Partially correct |
71 ms |
328 KB |
Output is partially correct |
| 7 |
Partially correct |
73 ms |
324 KB |
Output is partially correct |
| 8 |
Partially correct |
77 ms |
320 KB |
Output is partially correct |
| 9 |
Partially correct |
70 ms |
320 KB |
Output is partially correct |
| 10 |
Partially correct |
68 ms |
320 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
200 KB |
Output is correct |
| 2 |
Incorrect |
44 ms |
288 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
47 ms |
320 KB |
Output is partially correct |
| 2 |
Incorrect |
84 ms |
288 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
