Submission #400816

#	Time	Username	Problem	Language	Result	Execution time	Memory
400816		my99n	Koala Game (APIO17_koala)	C++14	72 / 100	105 ms	440 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
int b[110], r[110];
 
void clear () {
  memset(b, 0, sizeof b);
  memset(r, 0, sizeof r);
}
 
int minValue(int N, int W) {
  clear();
  b[0] = 1; playRound(b, r);
  if (r[0] != 2) return 0;
  for (int i = 0; i < N; i++) {
    if (r[i] == 0) return i;
  }
  return -1;
}
 
int maxValue(int N, int W) {
  clear();
  vector<int> t;
  for (int i = 0; i < N; i++) b[i] = 1;
  playRound(b, r);
  for (int i = 0; i < N; i++) {
    if (r[i] > b[i]) t.push_back(i);
  }
 
  clear();
  for (auto x : t) b[x] = 2;
  playRound(b, r);
  t.clear();
  for (int i = 0; i < N; i++) {
    if (r[i] > 2) t.push_back(i);
  }
 
  clear();
  for (auto x : t) b[x] = 4;
  playRound(b, r);
  t.clear();
  for (int i = 0; i < N; i++) {
    if (r[i] > 4) t.push_back(i);
  }
 
  clear();
  for (auto x : t) b[x] = 11;
  playRound(b, r);
  t.clear();
  for (int i = 0; i < N; i++) {
    if (r[i] > 11) t.push_back(i);
  }
  
  return t[0];
}
 
int solve (int aa, int bb, int x) {
  int n = 100, w = 100;
  vector<int> gr;
  clear();
  gr.clear();
  b[aa] = x, b[bb] = x;
  playRound(b, r);
  // for (int i = 0; i < n; i++) if (r[i] == 1) one.push_back(i);
  for (int i = 0; i < n; i++) if (r[i] > 1 and r[i] > b[i]) gr.push_back(i); 
  if (gr.size() == 1) {
    if (gr[0] == aa) return 0;
    else return 1;
  }
  if (gr.size() == 0) return -100;
  if (gr.size() == 2) return 100;
  assert(false);
}
 
bool compare(int aa, int bb) {

 
  int n = 100, w = 100;
  // int mn = minValue(n, w)
 
  int s3 = solve(aa, bb, 3);
  // cerr << "s3 " << s3 << endl;
  if (s3 == 100) {
    int s6 = solve(aa, bb, 6);
    // cerr << "s6 " << s6 << endl;
    if (s6 == 100) return solve(aa, bb, 10);
    return s6;
  }
  else if (s3 == -100) {
    int mn = minValue(n, w);
    if (mn == aa) return 1;
    if (mn == bb) return 0;
 
    return solve(aa, bb, 2);
  }
  return s3;

}

bool compare2 (int aa, int bb) {
  int n = 100, w = 200;
  clear(); b[aa] = n; b[bb] = n;
  playRound(b, r);
  if (r[aa] > n) return 0;
  else return 1;
}
 
int greaterValue(int N, int W) {
  return compare(0, 1);
}

void getFirst10 (int * P) {
  int n = 100;
  clear();
  int x = 1;
  for (int k = 1; k <= 10; k++) {

    while (P[x] != 0) x++;
    int mn = -1;

    // cerr << k << ' ' << x << endl;

    for (int i = 0; i < n; i++) if (P[i] != 0) b[i] = k;
    b[x] = k; playRound(b, r); b[x] = 0;

    for (int i = 0; i < n; i++) {
      if (P[i]) continue;
      if (r[i] == 0) mn = i;
    }
    assert(mn != -1);
    P[mn] = k;

  }
}

vector<int> v;
void mergesort (int l, int r) {
  if (l == r) return;
  int mid = (l+r)/2;
  mergesort(l, mid); mergesort(mid+1, r);
  
  int i = l, j = mid+1;
  vector<int> temp = vector<int> ();
  temp.clear();

  while (i <= mid and j <= r) {
    if (compare2(v[i], v[j])) {
      temp.push_back(v[i]); i++;
    }
    else {
      temp.push_back(v[j]); j++;
    }
  }
  while (i <= mid) {
    temp.push_back(v[i]); i++;
  }
  while (j <= r) {
    temp.push_back(v[j]); j++;
  }
  for (int i = l; i <= r; i++) {
    v[i] = temp[i-l];
  }
}

void mergesort2 (int l, int r) {
  if (l == r) return;
  int mid = (l+r)/2;
  mergesort2(l, mid); mergesort2(mid+1, r);
  
  int i = l, j = mid+1;
  vector<int> temp = vector<int> ();
  temp.clear();

  while (i <= mid and j <= r) {
    if (compare(v[i], v[j])) {
      temp.push_back(v[i]); i++;
    }
    else {
      temp.push_back(v[j]); j++;
    }
  }
  while (i <= mid) {
    temp.push_back(v[i]); i++;
  }
  while (j <= r) {
    temp.push_back(v[j]); j++;
  }
  for (int i = l; i <= r; i++) {
    v[i] = temp[i-l];
  }
}

void allValues(int N, int W, int *P) {
  if (W == 2*N) {

    v.clear();
    for (int i = 0; i < N; i++) v.push_back(i);
    // sort(v.begin(), v.end(), compare2);
    mergesort(0, N-1);

    // for (int i = 0; i < N; i++) cerr << v[i] << ' '; cerr << endl;
    for (int i = 0; i < v.size(); i++) {
      P[v[i]] = i+1;
    }
    
  } else {
    
    v.clear();
    for (int i = 0; i < N; i++) P[i] = 0;

    getFirst10(P);

    // for (int i = 0; i < N; i++) cerr << P[i] << ' '; cerr << endl;

    for (int i = 0; i < N; i++) {
      if (P[i]) continue;
      v.push_back(i);
    }
    // for (auto x : v) cerr << x << ' '; cerr << endl;
    // sort(v.begin(), v.end(), compare);
    mergesort2(0, v.size()-1);
    for (int i = 0; i < v.size(); i++) {
      P[v[i]] = i+11;
    }
  }
  return;
}

Compilation message (stderr)

koala.cpp: In function 'int solve(int, int, int)':
koala.cpp:58:16: warning: unused variable 'w' [-Wunused-variable]
   58 |   int n = 100, w = 100;
      |                ^
koala.cpp: In function 'bool compare2(int, int)':
koala.cpp:101:16: warning: unused variable 'w' [-Wunused-variable]
  101 |   int n = 100, w = 200;
      |                ^
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:202:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
koala.cpp:222:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

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