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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 |