Submission #1173811


Source Code Expand

#include <iostream>
#include <cstdlib>

#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <iostream>
#include <fstream>
#include <unistd.h>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include "sys/time.h"
using namespace std;
#define ITER(l,i) for(decltype(l.begin()) i=l.begin();i!=l.end();i++)
#define HERE (cerr << "LINE: " << __LINE__ << endl)

typedef long long ll_t;
typedef unsigned long long ull_t;

#ifdef LOCAL
#define msg(x) (x)
#else
#define msg(x)
#endif

#define DBG(x) cerr << #x << ": " << x << endl

struct timeval timer_begin, timer_end;
int timer_called;
inline void timer_start() 
{
  timer_called++;
  gettimeofday(&timer_begin, NULL);    
}     
inline double timer_now() 
{         
  timer_called++;
  gettimeofday(&timer_end, NULL);         
  return timer_end.tv_sec - timer_begin.tv_sec +
    (timer_end.tv_usec - timer_begin.tv_usec)/1000000.0;     
}

template<class T>
const T& clamp(const T& v,const T& lo,const T& hi) {
  return (v < lo) ? lo : (v > hi) ? hi : v;
}
unsigned int hash_function(unsigned long p) {
  // xor32()
  p ^= p<<7;
  p ^= p>>1;
  p ^= p<<25;
  unsigned int c = __builtin_popcount(p);
  return p<<c | p>>(32-c);
}
unsigned long long hash_function64(unsigned long long p) {
  // xor64()
  p ^= p<<16;
  p ^= p>>7;
  p ^= p<<39;
  unsigned long long c = __builtin_popcount(p);
  return p<<c | p>>(64-c);
}  

struct xor128_t {
  unsigned long long x, y, z, w;

  xor128_t(int seed=0) : x(123456789^seed) , y(362436069), z(521288629), w(88675123) {
    for (int i=0; i<48; i++)
      get();
  }

  void init(int seed) {
    x = 123456789^seed;
    y = 362436069;
    z = 521288629;
    w = 88675123;

    for (int i=0; i<48; i++)
      get();
  }

  inline unsigned long long get() {
    unsigned long long t=(x^(x<<11)); x=y; y=z; z=w;
    return (w=(w^(w>>19))^(t^(t>>8)));
  }

  inline unsigned long long get(unsigned int sz) {
    if (sz <= 1)
      return 0;

    unsigned long long x;
    const unsigned long long mask = (1<<(ilogb(sz-1)+1)) - 1;
    //cout << sz << " " << mask << endl;
    assert(mask >= (sz-1) && mask < 2*sz-1);
    do {
      x = get() & mask;
    } while (x >= sz);

    return x;
  }

  inline unsigned long long get(int beg,int end) {
    return get(end-beg) + beg;
  }

  double get_double() {
    static const double double_factor = 1.0 / (1.0 + 0xffffffffffffffffuLL);
    return get() * double_factor;
  }

  template<typename T> void shuffle(vector<T>& v,int partial=-1) {
    int sz = v.size();
    if (partial < 0 || partial > sz)
      partial = sz;

    for (int i=0; i<partial; i++) {
      swap(v[i], v[i + get(sz-i)]);
    }

  }
};

struct uf_t {
  vector <int16_t> parent;

  void clear() {
    parent.clear();
  }

  void add(int elm) {
    if (elm >= parent.size()) 
      parent.resize(elm+1, -1);
  }

  void merge(int a,int b) {
    add(a);
    add(b);

    int ia = a;
    int ib = b;

    if ((ia^ib)&1) swap(ia, ib);  // ok?
      
    int ra = root(ia);
    int rb = root(ib);

    if (ra != rb) {
      parent[ra] += parent[rb];
      parent[rb] = ra;
    }
  }

  int size(int elm) {
    return -parent[root(elm)];
  }

  int id(int elm) {
    return root(elm);
  }

  int root(int ia) {
    add(ia);
    return (parent[ia] < 0) ? ia : (parent[ia] = root(parent[ia]));
  }
};

template <typename Score_t,typename Item_t,typename HashFunc_t>
struct best_k_t {
  vector<pair<Score_t,int>> v;
  vector<Item_t> items;
  HashFunc_t hashfunc;
  set<uint32_t> used;
  bool never_push;

  best_k_t() : never_push(false) {}

  void push_force(const Score_t sc,const Item_t& e) {
    int id = items.size();
    items.push_back(e);

    int n = v.size();
    v.push_back(pair<Score_t,int>(sc,id));

    int m = (n+1)/2 - 1;
    while (n > 0 && v[n] < v[m]) {
      swap(v[n], v[m]);
      n = m;
      m = (n+1)/2 - 1;
    }
  }

  bool push(const Score_t sc,const Item_t& e,int w) {
    assert(!never_push);
    if (v.size() < w) {
      auto h = hashfunc(e);
      if (!used.count(h)) {
	used.insert(h);
	push_force(sc, e);
	return true;
      } else {
	return false;
      }
    } else if (sc > v[0].first) {
      auto h = hashfunc(e);
      if (!used.count(h)) {
	int id = v[0].second;
	v[0].first = sc;
	items[id] = e;
	used.insert(h);
	rebuild();
	return true;
      } else {
	return false;
      }
    }
    return false;
  }

  bool match(const Score_t sc,int w) {
    return (v.size() < w || sc > v[0].first);
  }

  void rebuild() {
    int n = 0;
    while (true) {
      int L = (n+1)*2 - 1;
      int R = L+1;

      if (L >= v.size()) 
	break;

      int m = (R >= v.size() || v[L] < v[R]) ? L : R;

      if (v[m] < v[n]) {
	swap(v[m], v[n]);
	n = m;
      } else {
	break;
      }
    }
  }

  Item_t pop() {
    // fix me
    never_push = true;
    
    int id = v[0].second;
    Item_t ret = items[id];

    v[0] = v.back();
    v.pop_back();

    rebuild();

    return ret;
  }
  Item_t top() { return v[0].second; }

  Item_t best() const {
    int best_i = 0;
    for (int i=0; i<v.size(); i++) {
      if (v[i] < v[best_i])
	best_i = i;
    }
    return items[v[best_i].second];
  }

  void clear() { v.clear(); }
  bool empty() const { return v.empty(); }
  int size() const { return v.size(); }
};

template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[ ";
  for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " ]"; 
  return os; 
}
template<typename T> ostream& operator<<(ostream& os, const set<T>& v) {
  os << "{ ";
  for(typename set<T>::const_iterator it=v.begin(); it!=v.end(); ++it) {
    if (it != v.begin())
      os << ", ";
    os << *it; 
  }
  os << " }"; 
  return os; 
}
template<typename T1,typename T2> ostream& operator<<(ostream& os, const pair<T1,T2>& v) {
  os << "[ " << v.first << ", " << v.second << "]";
  return os; 
}

#ifdef LOCAL
double TIME_LIMIT_FACTOR = 0.55;
#else
double TIME_LIMIT_FACTOR = 1.0;
#endif
double TIME_LIMIT = TIME_LIMIT_FACTOR * 10.0;

/* insert here */
int D, T;
const int N = 8;

vector<string> set_operations(int D,int T,vector<int> caps,vector<int> vals) {
  vector<tuple<int,int,vector<int>>> que, que2;
  DBG(D);
  DBG(T);
  DBG(caps);
  DBG(vals);
  que.emplace_back(0, 0, vector<int>());
  for (int t=0; t<N; t++) {
    que2 = que;
    for (const auto tu : que) {
      
      int v = get<0>(tu);
      int o = get<1>(tu);
      vector<int> ops = get<2>(tu);
      //cerr << v << " " << o << " " << ops << endl;

      if (vals[t] > 0 && v+vals[t] <= D) {
	ops.push_back(t);
	que2.emplace_back(v+vals[t], o, ops);
	ops.pop_back();
      }

      if (v+caps[t] <= D && o<T-1) {
	ops.push_back(~t);
	que2.emplace_back(v+caps[t], o+1, ops);
	ops.pop_back();
      }
    }

    que.swap(que2);
  }

  vector<int> best_ops;
  int best_o = 12345; // INF
  for (const auto& tu : que) {
    int v = get<0>(tu);
    int o = get<1>(tu);
    const vector<int>& ops = get<2>(tu);
    if (v != D)
      continue;

    if (o < best_o) {
      cerr << "BEST: " << v << " " << o << " " << ops << endl;
      best_o = o;
      best_ops = ops;
    }
  }
  //usleep(1000*1000);
  
  if (best_ops.empty())
    return {};

  if (best_o > 0 && D*D/(best_o+1) < 200) {
    cerr << "score_low" << endl;
    return {};
  }

  vector<string> ret;
  {
    string s;
    s = "sell ";
    s += to_string(best_ops.size());
    for (auto x : best_ops) {
      s += " ";
      s += to_string(((x < 0) ? ~x : x)+1);
    }
    ret.push_back(s);
  }
  for (auto x : best_ops) {
    if (x < 0)
      ret.push_back("fill "+to_string((~x)+1));
  }
  
  return ret;
}			      

string operate(int D,int T,vector<int> caps,vector<int> vals) {
  static vector<string> operations;
  static xor128_t rng;
  if (operations.empty())
    operations = set_operations(D, T, caps, vals);

  if (!operations.empty()) {
    auto op = operations.back();
    operations.pop_back();
    return op;
  } else {
    int a = rng.get(N);
    int b = rng.get(N);
    if (a != b && caps[a] == caps[b] && vals[b] == 0)
      return "change "+to_string(b+1);
    else {
      vector<int> ord(N);
      iota(ord.begin(), ord.end(), 0);
      rng.shuffle(ord);
      for (int i=0; i<N; i++)
	if (vals[ord[i]] == 0) 
	  return "fill "+to_string(ord[i]+1);
      return "pass";
    }
  }
}

int main()
{
  vector<int> caps(N);
  vector<int> vals(N);
  for (int lp=0; lp<1000; lp++) {
    cin >> D >> T;
    for (int i=0; i<N; i++)
      cin >> caps[i];
    for (int i=0; i<N; i++)
      cin >> vals[i];

    auto op = operate(D, T, caps, vals);
    cerr << op << endl;
    cout << op << endl;
  }
}

Submission Info

Submission Time
Task A - 石油王Xの憂鬱
User yowa
Language C++14 (GCC 5.4.1)
Score 5331244
Code Size 9195 Byte
Status AC
Exec Time 246 ms
Memory 1476 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10 test_11 test_12 test_13 test_14 test_15 test_16 test_17 test_18 test_19 test_20 test_21 test_22 test_23 test_24 test_25 test_26 test_27 test_28 test_29 test_30 test_31 test_32 test_33 test_34 test_35 test_36 test_37 test_38 test_39 test_40 test_41 test_42 test_43 test_44 test_45 test_46 test_47 test_48 test_49 test_50
Score / Max Score 104840 / 417500 106706 / 417500 112598 / 417500 104762 / 417500 105431 / 417500 106747 / 417500 114038 / 417500 103902 / 417500 112222 / 417500 112602 / 417500 113341 / 417500 107966 / 417500 106707 / 417500 109954 / 417500 107350 / 417500 104369 / 417500 104948 / 417500 101854 / 417500 106050 / 417500 102616 / 417500 115537 / 417500 105054 / 417500 103801 / 417500 107404 / 417500 113589 / 417500 98661 / 417500 105567 / 417500 105687 / 417500 106558 / 417500 107958 / 417500 111309 / 417500 102973 / 417500 105739 / 417500 99394 / 417500 111139 / 417500 110008 / 417500 110680 / 417500 101874 / 417500 103677 / 417500 97481 / 417500 101895 / 417500 100074 / 417500 112503 / 417500 106478 / 417500 109229 / 417500 104001 / 417500 114011 / 417500 99913 / 417500 106315 / 417500 103732 / 417500
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
test_11 subtask_01_11.txt
test_12 subtask_01_12.txt
test_13 subtask_01_13.txt
test_14 subtask_01_14.txt
test_15 subtask_01_15.txt
test_16 subtask_01_16.txt
test_17 subtask_01_17.txt
test_18 subtask_01_18.txt
test_19 subtask_01_19.txt
test_20 subtask_01_20.txt
test_21 subtask_01_21.txt
test_22 subtask_01_22.txt
test_23 subtask_01_23.txt
test_24 subtask_01_24.txt
test_25 subtask_01_25.txt
test_26 subtask_01_26.txt
test_27 subtask_01_27.txt
test_28 subtask_01_28.txt
test_29 subtask_01_29.txt
test_30 subtask_01_30.txt
test_31 subtask_01_31.txt
test_32 subtask_01_32.txt
test_33 subtask_01_33.txt
test_34 subtask_01_34.txt
test_35 subtask_01_35.txt
test_36 subtask_01_36.txt
test_37 subtask_01_37.txt
test_38 subtask_01_38.txt
test_39 subtask_01_39.txt
test_40 subtask_01_40.txt
test_41 subtask_01_41.txt
test_42 subtask_01_42.txt
test_43 subtask_01_43.txt
test_44 subtask_01_44.txt
test_45 subtask_01_45.txt
test_46 subtask_01_46.txt
test_47 subtask_01_47.txt
test_48 subtask_01_48.txt
test_49 subtask_01_49.txt
test_50 subtask_01_50.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 205 ms 1428 KB
subtask_01_02.txt AC 225 ms 1440 KB
subtask_01_03.txt AC 208 ms 1456 KB
subtask_01_04.txt AC 222 ms 1444 KB
subtask_01_05.txt AC 220 ms 1352 KB
subtask_01_06.txt AC 196 ms 1476 KB
subtask_01_07.txt AC 200 ms 1336 KB
subtask_01_08.txt AC 230 ms 1452 KB
subtask_01_09.txt AC 210 ms 1432 KB
subtask_01_10.txt AC 198 ms 1396 KB
subtask_01_11.txt AC 203 ms 1436 KB
subtask_01_12.txt AC 207 ms 1324 KB
subtask_01_13.txt AC 216 ms 1428 KB
subtask_01_14.txt AC 202 ms 1416 KB
subtask_01_15.txt AC 211 ms 1428 KB
subtask_01_16.txt AC 219 ms 1444 KB
subtask_01_17.txt AC 210 ms 1420 KB
subtask_01_18.txt AC 229 ms 1420 KB
subtask_01_19.txt AC 197 ms 1344 KB
subtask_01_20.txt AC 184 ms 1448 KB
subtask_01_21.txt AC 202 ms 1412 KB
subtask_01_22.txt AC 213 ms 1440 KB
subtask_01_23.txt AC 217 ms 1368 KB
subtask_01_24.txt AC 212 ms 1340 KB
subtask_01_25.txt AC 196 ms 1348 KB
subtask_01_26.txt AC 216 ms 1440 KB
subtask_01_27.txt AC 207 ms 1328 KB
subtask_01_28.txt AC 198 ms 1400 KB
subtask_01_29.txt AC 207 ms 1432 KB
subtask_01_30.txt AC 192 ms 1428 KB
subtask_01_31.txt AC 183 ms 1400 KB
subtask_01_32.txt AC 222 ms 1376 KB
subtask_01_33.txt AC 246 ms 1392 KB
subtask_01_34.txt AC 217 ms 1444 KB
subtask_01_35.txt AC 190 ms 1448 KB
subtask_01_36.txt AC 209 ms 1420 KB
subtask_01_37.txt AC 215 ms 1352 KB
subtask_01_38.txt AC 206 ms 1420 KB
subtask_01_39.txt AC 208 ms 1400 KB
subtask_01_40.txt AC 225 ms 1408 KB
subtask_01_41.txt AC 236 ms 1420 KB
subtask_01_42.txt AC 218 ms 1436 KB
subtask_01_43.txt AC 193 ms 1444 KB
subtask_01_44.txt AC 216 ms 1460 KB
subtask_01_45.txt AC 157 ms 1432 KB
subtask_01_46.txt AC 211 ms 1424 KB
subtask_01_47.txt AC 195 ms 1316 KB
subtask_01_48.txt AC 226 ms 1384 KB
subtask_01_49.txt AC 198 ms 1376 KB
subtask_01_50.txt AC 208 ms 1352 KB