제출 #525556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
525556		obokaman	커다란 상품 (IOI17_prize)	C++17	100 / 100	243 ms	712 KiB

prize

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include "prize.h"
#include <random>

using namespace std;


std::default_random_engine generator;

set<int> seen;

typedef pair<int,int> pii;
struct Info {
  int lefthighercount = 0;
  int righthighercount = 0;
};

typedef map<int, Info> Level;
map<int, Level> levels;

void debug() {
  cerr << "Seen: ";
  for (int x: seen) cerr << x << " ";
  cerr << endl;
  cerr << "Levels: " << endl;
  for (auto& s: levels) {
    cerr << "v=" << s.first << ": ";
    for (auto& p: s.second) {
      cerr << p.first << "(" << p.second.lefthighercount << ","
           << p.second.righthighercount << ") ";
    }
    cerr << endl;
  }
  cerr << endl;
}

int count(int a, int b) {
  auto itfrom = seen.lower_bound(a);
  auto itto = seen.lower_bound(b);
  int num=0;
  while (itfrom != itto) {
    ++num;
    ++itfrom;
  }
  return num;
}


// Randomly find some interval in level within [ca,cb) that
// is a good candidate to query.
pii findinterval(int ca, int cb, const Level& l) {
  auto it = l.upper_bound(ca);
  --it;
  //  cerr << "Level" << endl;
  vector<pii> candidates;
  while(it->first + 1 < cb) {
    int a = it->first + 1;
    int lefta = it->second.lefthighercount;
    ++it;
    int b = it->first;
    int leftb = it->second.lefthighercount;
    if (a == b) continue;
    //    int l = b - a;  // #spots
    //   l -= count(seen, a, b);  // l = #empty spots
    int goodones = leftb - lefta;
    //    cerr << "[" << a << "," << b << "): " << goodones << " goodones" << endl;
    if (goodones > 0 && (count(a, b) < b - a)) {
      candidates.push_back({a, b});
    }
  }
  if (candidates.size() == 0) {
    return {-1, -1};
  }
  uniform_int_distribution<int> distribution(0, candidates.size()-1);
  auto p = candidates[distribution(generator)];
  return {max(p.first, ca), min(p.second, cb)};
}


int find_best(int n) {
  while (1) {
    //        debug();
    //    cerr << "XXX" << endl;
    int a = 0, b = n;
    if (!seen.empty()) {
      do {
        a = 0, b = n;
        for (auto it = levels.begin(); it != levels.end(); ++it) {
          tie(a, b) = findinterval(a, b, it->second);
          //          cerr << "Level " << it->first << ": [" << a << "," << b << ")"
          //   << endl;
          if (a == -1 && b == -1) break;
        }
        //        cerr << "." << endl;
      } while (a == -1 && b == -1);
    }
    // find best spot in [a, b)
    int m = (a+b)/2;
    int next = 1;
    int signnext = 1;
    //    cerr << "Checking " << m << "..." << endl;
    while (m < a || m >= b || seen.find(m) != seen.end()) {
      m += signnext * next;
      ++next;
      signnext *= -1;
      //cerr << "Taken. Checking " << m << "..." << endl;
    }
    auto q = ask(m);
    seen.insert(m);
    int v = q[0]+q[1];
    if (v == 0) return m;
    auto& s = levels[v];
    if (s.empty()) {
      s[-1] = Info{0, q[0]+q[1]};
      s[n] = Info{q[0]+q[1], 0};
    }
    s[m] = Info{q[0], q[1]};
  }
}

// int find_best(int n) {
//   int m = n/2;
//   auto q = ask(m);
//   seen.insert(m);
//   int v = q[0]+q[1];
//   if (v == 0) return m;
//   {
//     auto& s = intervals[v];
//     s[-1] = Info{0, q[0]+q[1]};
//     s[m] = Info{q[0], q[1]};
//     s[n] = Info{q[0]+q[1], 0};
//   }
//   while (1) {
//     debug();
//     auto its = intervals.end();
//     --its;
//     auto& s = its->second;
//     double bestscore = 0;
//     auto bestit = s.end();
//     for (auto it = s.begin(); it->first != n;) {
//       int a = it->first + 1;
//       int lefta = it->second.lefthighercount;
//       ++it;
//       int b = it->first;
//       int leftb = it->second.lefthighercount;
//       int l = b - a;  // #spots
//       l -= count(seen, a, b);  // l = #empty spots
//       cerr << "[" << a << "," << b << "): " << l << " empty   ";
//       int goodones = leftb - lefta;
//       cerr << goodones << " goodones" << endl;
//       if (l > 0 || goodones > 0) {
//         if (goodones > 0) {
//           double score = ((double)goodones)/(l+1);
//           if (score > bestscore) {
//             bestit = it;
//             bestscore = score;
//             cerr << "bestscore: " << bestscore << endl;
//           }
//         }
//       }
//     }
//     // find best spot in [ita, itb)
//     auto ita = bestit, itb = bestit;
//     --ita;
//     int a = ita->first+1;
//     int b = itb->first;
//     int m = (a+b)/2;
//     int next = 1;
//     int signnext = 1;
//     while (m < a || m >= b || seen.find(m) != seen.end()) {
//       m += signnext * next;
//       ++next;
//       signnext *= -1;
//     }
//     auto q = ask(m);
//     seen.insert(m);
//     int v = q[0]+q[1];
//     if (v == 0) return m;
//     auto& s2 = intervals[v];
//     if (s2.empty()) {
//       s2[-1] = Info{0, q[0]+q[1]};
//       s2[n] = Info{q[0]+q[1], 0};
//     }
//     s2[m] = Info{q[0], q[1]};
//   }
// }



// int find_best(int n) {
//   if (segments.empty()) {
//     int m = n/2;
//     auto q = ask(m);
//     int v = q[0]+q[1];
//     if (v == 0) return m;
//     segments[v][{0, m}] = Info{q[0], 0, q[1]};
//     segments[v][{m+1, n}] = Info{q[1], q[0], 0};
//   }
//   while (1) {
//     auto its = segments.end();
//     --its;
//     auto& s = its->second;
//     double bestp = 0;
//     auto bestit = s.end();
//     for (auto it = s.begin(); it != s.end(); ++it) {
//       int l = it->first.second - it->first.first;
//       if (l > 0) {
//         double p = ((double)it->second.higher)/l;
//         if (p>bestp) {
//           bestit = it;
//           bestp = p;
//         }
//       }
//     }
//     auto x = bestit->first;
//     auto oldinfo = bestit->second;
//     int m = (x.first+x.second)/2;
//     auto q = ask(m);
//     int v = q[0] + q[1];
//     if (v == 0) return m;
//     // fix here, different v.
//     s.erase(bestit);
//     s[{x.first, m}] = Info{q[0]-oldinfo.leftsum, oldinfo.leftsum, q[1]};
//     s[{m+1, x.second}] = Info{q[1]-oldinfo.rightsum, q[0], oldinfo.rightsum};
//   }
//   return -1;
// }

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80