Instantly share code, notes, and snippets.

@teapotd /a2.cpp Secret
Created Jul 31, 2018

Embed
What would you like to do?
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("avx")
template<class T>struct _iter_wrapper{T begin_,end_;T begin(){return begin_;}T end(){return end_;}};
template<class T>_iter_wrapper<const T*>span(const T*arr, int n){return _iter_wrapper<const T*>{arr,
arr+n};} template<class T, int N>_iter_wrapper<const T*>span(const T(&arr)[N]) {return span(arr,N);}
#define _deb(...)(_printDebug/* */(__LINE__,#__VA_ARGS__,__VA_ARGS__))
#define rep(i,b,e)/* */for(int i=(b);i<(e);i++)
#define sz(x)/* */int((x).size())
#define mp/* */make_pair
#include/* */<bits/stdc++.h>
#ifdef/* */LOC
#define/* */deb _deb
#elif/* */true
#define/* */deb(...)
#endif/* */
#define/* */x first
#define/* ("`-''-/").___..--''"`-._ */y second
#define pb/* `6_ 6 ) `-. ( ).`-.__.`) */push_back
#define each(a,x/* (_Y_.)' ._ ) `._ `. ``-..-` */)for(auto&a:(x))
#define all(x)(x)/* _..`--'_..-_/ /--'_.' ,' */.begin(),(x).end()
#define DBP(...)void print(/* (il),-'' (li),' ((!.-' */...){DD(#__VA_ARGS__,__VA_ARGS__);}
using namespace std;using namespace rel_ops;using ll=long long;using ull=unsigned long long;using Vi
=vector<int>;using Vll=vector<ll>;using Vull=vector<ull>; using Pii=pair<int,int>; template<class T,
class V> auto operator<<(T& out,V val)->decltype(val.print(0),out){out<<"{";val.print();return out<<
"}";}template<class T, class V>auto operator<<(T&out,V val)->decltype(get<1>(val), out){return out<<
"("<<val.x<<", "<<val.y<<")";} template<class T,class V>auto operator<<(T &out,V val)->decltype(all(
val),out){out << "[";bool comma=false;for(auto elem:val){if(comma)out << ", ";out<<elem;comma=true;}
return out<<"]";}void DD(...){}template<class T,class...S>void DD(const char*format,T elem,S...rest)
{int braces=0;while(*format&&(braces>0||*format!=',')){if(*format=='('||*format=='['||*format=='{'||
*format=='<'){braces++;}if (*format==')'||*format==']'||*format=='}'||*format=='>') braces--;cerr<<*
format++;} cerr<<": "<<elem<<*format++;DD(format, rest...);} template<class...T>void _printDebug(int
line,const char*format, T...elems){cerr<<'<';if(line<10)cerr<<'0';if(line<100)cerr<<'0';cerr<<line<<
"> ";DD(format,elems...);cerr<<endl;}void run();int main(){cin.sync_with_stdio(0); cin.tie(0);cout<<
fixed<<setprecision(/**********************> by teapotd <**********************/10);run();return 0;}
//------------------------------------------------------------------------------------------------//
constexpr int MAX_STRIPE = 100000;
constexpr int MAX_BACKPACK = 10000;
constexpr int MAX_COLORS = 10;
constexpr int MAX_HAND = 10;
constexpr int MAX_ELEMS = 10;
constexpr int MAX_BOTTLES = MAX_HAND + MAX_BACKPACK;
struct State {
uint16_t pos[MAX_ELEMS];
uint8_t sorted[MAX_ELEMS];
uint8_t inHand[MAX_COLORS];
uint16_t cur;
};
int nStripe, nBackpack, nColors, nHand, nElems;
uint8_t stripe[MAX_STRIPE];
uint16_t jumps[MAX_STRIPE][MAX_COLORS];
uint8_t bottles[MAX_BOTTLES];
State* state;
bitset<MAX_STRIPE> used;
int solve();
void initState(State& st) {
memset(st.inHand, 0, sizeof(uint8_t)*nHand);
rep(i, 0, nHand) st.inHand[bottles[i]]++;
rep(i, 0, nElems) st.pos[i] = uint16_t(i);
iota(st.sorted, st.sorted+nElems, 0);
st.cur = 0;
}
void setState(State* st) {
if (state) {
rep(i, 0, nElems) used.reset(state->pos[i]);
}
if (st) {
rep(i, 0, nElems) used.set(st->pos[i]);
state = st;
}
}
int getMinPos() {
int ret = INT_MAX;
rep(i, 0, nElems) ret = min(ret, int(state->pos[i]));
return ret;
}
int getSumPos() {
int ret = 0;
rep(i, 0, nElems) ret += state->pos[i];
return ret;
}
template<bool perform = true>
int makeMove(int elem, int color) {
assert(state);
assert(state->cur < nBackpack);
assert(state->inHand[color]);
int src = state->pos[elem];
int dst = src;
if (perform) used.reset(dst);
do {
dst = jumps[dst][color];
} while (used[dst]);
if (perform) {
used.set(dst);
state->pos[elem] = int16_t(dst);
state->inHand[color]--;
state->inHand[bottles[nHand+state->cur]]++;
state->cur++;
}
return dst-src;
}
int caseNum = 0;
int runCase(int n) {
string stripeStr, bottlesStr;
cin >> nBackpack >> nColors >> nHand >> nElems;
cin >> stripeStr >> bottlesStr;
nStripe = n;
rep(i, 0, nStripe) stripe[i] = uint8_t(stripeStr[i] - 'A');
rep(i, 0, nHand+nBackpack) bottles[i] = uint8_t(bottlesStr[i] - 'A');
rep(i, 0, nColors) jumps[0][i] = 0;
rep(k, 0, 2) {
for (int i = nStripe-1; i >= 0; i--) {
int next = (i+1 < nStripe ? i+1 : 0);
rep(c, 0, nColors) jumps[i][c] = uint16_t(jumps[next][c]);
jumps[i][stripeStr[next]-'A'] = uint16_t(next);
}
}
state = nullptr;
used.reset();
int score = solve();
deb(++caseNum, score);
return score;
}
void run() {
int n; cin >> n;
ll sum = 0;
if (n < 0) {
n = -n;
rep(i, 0, n) {
int k; cin >> k;
sum += runCase(k);
}
} else {
sum += runCase(n);
n = 1;
}
#ifdef LOC
double avg = double(sum) / n;
deb(n, avg);
#endif
}
// -----
constexpr int SEARCH_WIDTH = 4000;
constexpr int SELECTION_STEP = 3;
constexpr int MAX_NEW_LAYER = SEARCH_WIDTH*MAX_ELEMS;
struct Move {
uint8_t elem, color;
int prev;
};
struct NextState {
Move move;
int score;
int16_t moveDst, toBubble;
};
Move moves[MAX_BACKPACK][SEARCH_WIDTH];
State layers[2][SEARCH_WIDTH];
int oldLayerSize;
NextState newLayer[MAX_NEW_LAYER];
vector<int> scoreCounts;
void advance(int level) {
auto& oldLayer = layers[~level&1];
auto& outLayer = layers[level&1];
int minScore = INT_MAX, maxScore = INT_MIN;
int total = 0;
rep(baseID, 0, oldLayerSize) {
auto& base = oldLayer[baseID];
int bestColors[MAX_ELEMS], bestDests[MAX_ELEMS];
memset(bestDests, 0, sizeof(bestDests));
rep(c, 0, nColors) if (base.inHand[c]) {
int dests[MAX_ELEMS];
rep(i, 0, nElems) {
int src = base.pos[base.sorted[i]];
int dst = jumps[src][c];
dests[i] = dst;
if (stripe[src] == c) {
rep(j, 0, i) if (dests[j] == src) dests[j] = dst;
}
}
rep(i, 0, nElems) if (dests[i] > bestDests[i]) {
bestDests[i] = dests[i];
bestColors[i] = c;
}
}
int sum = 0;
rep(e, 0, nElems) sum += base.pos[e];
rep(i, 0, nElems) {
auto& st = newLayer[total++];
st.move.prev = baseID;
st.move.elem = uint8_t(base.sorted[i]);
st.toBubble = int16_t(i);
int dst = bestDests[i];
st.move.color = uint8_t(bestColors[i]);
st.moveDst = int16_t(dst);
int newSum = sum + dst - base.pos[base.sorted[i]];
int greatest = max(dst, int(base.pos[base.sorted[nElems-1]]));
int least;
if (i == 0) {
least = min(dst, int(base.pos[base.sorted[1]]));
} else {
least = base.pos[base.sorted[0]];
}
st.score = newSum - (greatest-least)/2;
minScore = min(minScore, st.score);
maxScore = max(maxScore, st.score);
}
}
int cut = 0, nGreater = 0;
oldLayerSize = min(total, SEARCH_WIDTH);
int multipliedSize = min(total, SEARCH_WIDTH*SELECTION_STEP);
scoreCounts.assign(maxScore-minScore+2, 0);
rep(i, 0, total) scoreCounts[maxScore-newLayer[i].score]++;
while (nGreater + scoreCounts[cut] < multipliedSize) {
nGreater += scoreCounts[cut];
cut++;
}
int j = 0, nEqual = multipliedSize - nGreater;
cut = maxScore - cut;
int newBottle = bottles[nHand+level];
int counter = -1;
rep(i, 0, total) if (newLayer[i].score >= cut) {
auto& info = newLayer[i];
if (info.score == cut) {
if (nEqual <= 0) continue;
nEqual--;
}
if (++counter >= SELECTION_STEP) counter = 0;
if (counter != 0) continue;
auto& out = outLayer[j];
out = oldLayer[info.move.prev];
out.pos[info.move.elem] = info.moveDst;
out.inHand[info.move.color]--;
out.inHand[newBottle]++;
out.cur++;
rep(k, info.toBubble+1, nElems) {
if (out.pos[out.sorted[k-1]] > out.pos[out.sorted[k]]) {
swap(out.sorted[k-1], out.sorted[k]);
} else {
break;
}
}
moves[level][j] = info.move;
j++;
}
oldLayerSize = j;
}
void printState(State& st) {
#ifdef LOC
setState(&st);
double minScore = double(getMinPos()) / st.cur;
double avgScore = double(getSumPos()) / st.cur / nElems;
deb(st.cur, getMinPos(), minScore, avgScore, span(st.pos, nElems));
setState(nullptr);
#else
(void)st;
#endif
}
void printMove(int e, int c) {
#ifndef LOC
cout << e << ' ' << char(c+'A') << '\n';
#else
(void)e; (void)c;
#endif
}
void printMoves(int layerID, int id) {
int n = layers[layerID][id].cur;
stack<Move> path;
path.push(moves[n-1][id]);
for (int i = n-2; i >= 0; i--) {
path.push(moves[i][path.top().prev]);
}
while (!path.empty()) {
Move m = path.top();
path.pop();
printMove(m.elem, m.color);
}
}
int solve() {
memset(moves, 0, sizeof(moves));
memset(layers, 0, sizeof(layers));
rep(i, 0, SEARCH_WIDTH) initState(layers[1][i]);
oldLayerSize = SEARCH_WIDTH;
rep(i, 0, nBackpack) {
advance(i);
// if ((i % 100) == 99) printState(layers[i&1][0]);
}
int lastLayerID = (nBackpack-1) & 1;
auto& lastLayer = layers[lastLayerID];
int bestMin = INT_MAX, bestID = 0;
rep(i, 0, oldLayerSize) {
setState(&lastLayer[i]);
int alt = getMinPos();
if (alt > bestMin) {
bestMin = alt;
bestID = i;
}
}
printMoves(lastLayerID, bestID);
// printState(*state);
return getMinPos();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment