Submission #1179560
Source Code Expand
#include<iostream>
#include<algorithm>
#include<random>
#include<array>
#include<sstream>
#include<utility>
#include<set>
using namespace std;
constexpr int N=8;
mt19937 engine;
int count8(int x){
return __builtin_popcount(x);
}
struct S{
array<signed char,N> C,A;
int D,T;
int score;
int action;
unsigned cx,tx;
int escore;
S(const array<signed char,N> &c,const array<signed char,N> &a,int d,int t,int s,int paction,unsigned cidx,unsigned tidx):C(c),A(a),D(d),T(t),score(s),action(paction),cx(cidx),tx(tidx){
eval();
}
void eval(){
unsigned long long b=1;
for(int i=0;i<N;i++){
b|=b<<A[i];
}
int s=0;
for(int i=1;i<=50;i++){
if(b>>i&1){
s+=i*i;
}
}
escore=s/30+score;
}
bool operator<(const S &s)const{
return escore<s.escore;
}
};
template<class E>
void debug(const array<signed char,N> &C,const array<signed char,N> &A,const E &as){
stringstream ss;
// for(auto e:C){
// ss<<int(e)<<' ';
// }
// ss<<endl;
// for(auto e:A){
// ss<<int(e)<<' ';
// }
// ss<<endl;
int a[N+N+2]{};
for(const auto &e:as){
a[e.action]++;
}
ss<<a[0]<<'|';
for(int i=0;i<N-1;i++){
ss<<a[i+1]<<' ';
}
ss<<a[N]<<'|';
for(int i=0;i<N-1;i++){
ss<<a[i+1+N]<<' ';
}
ss<<a[N+N]<<'|';
ss<<a[N+N+1]<<endl;
cerr<<ss.str();
}
int main(){
for(int i=0;i<1000;i++){
int D,T;
cin>>D>>T;
array<signed char,N> C,A;
for(int j=0;j<N;j++){
int i;
cin>>i;
C[j]=i;
}
for(int j=0;j<N;j++){
int i;
cin>>i;
A[j]=i;
}
int sb=0;
{
unsigned long long b[N+1];
b[0]=1;
for(int i=0;i<N;i++){
b[i+1]=b[i]|b[i]<<A[i];
}
if(b[N]>>D&1){
for(int i=N-1,x=D;i>=0;i--){
if(!(b[i]>>x&1)){
sb|=1<<i;
x-=A[i];
}
}
}
}
constexpr int NM=8,QH=16,QW=38;
constexpr int NIA=N+N+2;
int eaction[NIA]{};
for(int nm=0;nm<NM;nm++){
vector<S> ques[QH];
constexpr int NRN=256;
int rnft[NRN],rnfc[NRN];
for(int i=0;i<NRN;i++){
rnft[i]=uniform_int_distribution<>(1,10)(engine);
rnfc[i]=uniform_int_distribution<>(0,499)(engine);
}
int nt=T-1;
int nd=D;
int cx=0;
if(nt==0){
cx=1;
nt=rnfc[0]%10+1;
nd=rnfc[0]/10+1;
}
ques[0].emplace_back(C,A,rnfc[0]/10+1,rnfc[0]%10+1,0,0,1,0);
{
set<pair<int,int> > dupe;
for(int i=0;i<N;i++){
if(dupe.emplace(C[i],A[i]).second){
if(A[i]!=C[i]){
auto ca=A;
ca[i]=C[i];
ques[0].emplace_back(C,ca,nd,nt,0,1+i,cx,0);
}
{
auto ca=A,cc=C;
cc[i]=rnft[0];
ca[i]=0;
ques[0].emplace_back(cc,ca,nd,nt,0,1+N+i,cx,1);
}
}
}
}
if(sb){
auto cc=C,ca=A;
int tx=0;
for(int i=0;i<N;i++){
if(sb>>i&1){
cc[i]=rnft[tx++];
ca[i]=0;
}
}
ques[0].emplace_back(cc,ca,rnfc[0]/10,rnfc[0]%10,D*D,1+N+N,1,tx);
}
int ceaction[NIA]{};
for(int i=0;i<QH-1;i++){
sort(ques[i].rbegin(),ques[i].rend());
for(int j=0;j<min<int>(QW,ques[i].size());j++){
const S &cs=ques[i][j];
{
auto ns=cs;
ns.D=rnfc[cs.cx%NRN]/10+1;
ns.T=rnfc[cs.cx%NRN]%10+1;
ns.cx++;
ns.eval();
ques[i+1].push_back(ns);
}
{
int nt=cs.T-1;
int nd=cs.D;
int ncx=cs.cx;
if(nt==0){
nt=rnfc[ncx%NRN]%10+1;
nd=rnfc[ncx%NRN]/10+1;
ncx+=1;
}
{
int x=-1;
int ccap=0;
for(int k=0;k<N;k++){
if(cs.A[k]!=cs.C[k]&&ccap<cs.C[k]){
x=k;
ccap=cs.C[k];
}
}
if(x>=0){
auto ns=cs;
ns.A[x]=ns.C[x];
ns.T=nt;
ns.D=nd;
ns.cx=ncx;
ns.eval();
ques[i+1].push_back(ns);
}
}
}
{
unsigned long long b[N+1];
b[0]=1;
for(int i=0;i<N;i++){
b[i+1]=b[i]|b[i]<<cs.A[i];
}
if(b[N]>>cs.D&1){
int sb=0;
for(int i=N-1,x=cs.D;i>=0;i--){
if(!(b[i]>>x&1)){
sb|=1<<i;
x-=cs.A[i];
}
}
auto ns=cs;
auto &cc=ns.C,&ca=ns.A;
for(int i=0;i<N;i++){
if(sb>>i&1){
cc[i]=rnft[ns.tx++%NRN];
ca[i]=0;
}
}
ns.score+=ns.D*ns.D;
ns.D=rnfc[cs.cx%NRN]/10+1;
ns.T=rnfc[cs.cx%NRN]%10+1;
ns.cx++;
ns.eval();
ques[i+1].push_back(ns);
}
}
}
for(auto &e:ques[i+1]){
ceaction[e.action]=max(ceaction[e.action],e.score);
}
}
for(int i=0;i<NIA;i++){
eaction[i]+=ceaction[i];
}
}
auto ba=max_element(begin(eaction),end(eaction))-begin(eaction);
if(ba==0){
cout<<"pass"<<endl;
}else if(ba<=N){
cout<<"fill "<<ba<<endl;
}else if(ba<=N+N){
cout<<"change "<<ba-N<<endl;
}else{
cout<<"sell "<<count8(sb);
for(int i=0;i<N;i++){
if(sb>>i&1){
cout<<' '<<i+1;
}
}
cout<<endl;
}
}
}
Submission Info
Submission Time |
|
Task |
A - 石油王Xの憂鬱 |
User |
ustimaw |
Language |
C++14 (GCC 5.4.1) |
Score |
7271819 |
Code Size |
5112 Byte |
Status |
AC |
Exec Time |
1600 ms |
Memory |
848 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 |
136840 / 417500 |
150389 / 417500 |
152445 / 417500 |
140532 / 417500 |
146703 / 417500 |
151217 / 417500 |
149202 / 417500 |
145631 / 417500 |
147230 / 417500 |
143177 / 417500 |
146390 / 417500 |
145413 / 417500 |
153224 / 417500 |
153991 / 417500 |
148543 / 417500 |
148762 / 417500 |
139978 / 417500 |
148080 / 417500 |
146267 / 417500 |
143542 / 417500 |
152408 / 417500 |
149467 / 417500 |
138596 / 417500 |
145803 / 417500 |
147863 / 417500 |
134093 / 417500 |
148293 / 417500 |
141357 / 417500 |
138519 / 417500 |
151872 / 417500 |
151295 / 417500 |
147250 / 417500 |
148193 / 417500 |
152869 / 417500 |
146723 / 417500 |
146121 / 417500 |
144010 / 417500 |
140478 / 417500 |
143481 / 417500 |
139369 / 417500 |
143990 / 417500 |
144642 / 417500 |
140833 / 417500 |
142018 / 417500 |
135454 / 417500 |
146032 / 417500 |
148841 / 417500 |
140111 / 417500 |
140945 / 417500 |
143337 / 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 |
1596 ms |
724 KB |
subtask_01_02.txt |
AC |
1587 ms |
720 KB |
subtask_01_03.txt |
AC |
1597 ms |
848 KB |
subtask_01_04.txt |
AC |
1593 ms |
848 KB |
subtask_01_05.txt |
AC |
1598 ms |
844 KB |
subtask_01_06.txt |
AC |
1589 ms |
840 KB |
subtask_01_07.txt |
AC |
1600 ms |
720 KB |
subtask_01_08.txt |
AC |
1589 ms |
840 KB |
subtask_01_09.txt |
AC |
1586 ms |
848 KB |
subtask_01_10.txt |
AC |
1589 ms |
848 KB |
subtask_01_11.txt |
AC |
1600 ms |
720 KB |
subtask_01_12.txt |
AC |
1591 ms |
720 KB |
subtask_01_13.txt |
AC |
1585 ms |
848 KB |
subtask_01_14.txt |
AC |
1594 ms |
724 KB |
subtask_01_15.txt |
AC |
1595 ms |
720 KB |
subtask_01_16.txt |
AC |
1589 ms |
848 KB |
subtask_01_17.txt |
AC |
1596 ms |
848 KB |
subtask_01_18.txt |
AC |
1587 ms |
720 KB |
subtask_01_19.txt |
AC |
1589 ms |
720 KB |
subtask_01_20.txt |
AC |
1586 ms |
720 KB |
subtask_01_21.txt |
AC |
1584 ms |
848 KB |
subtask_01_22.txt |
AC |
1590 ms |
848 KB |
subtask_01_23.txt |
AC |
1597 ms |
720 KB |
subtask_01_24.txt |
AC |
1589 ms |
844 KB |
subtask_01_25.txt |
AC |
1584 ms |
848 KB |
subtask_01_26.txt |
AC |
1597 ms |
724 KB |
subtask_01_27.txt |
AC |
1590 ms |
844 KB |
subtask_01_28.txt |
AC |
1592 ms |
724 KB |
subtask_01_29.txt |
AC |
1594 ms |
844 KB |
subtask_01_30.txt |
AC |
1594 ms |
848 KB |
subtask_01_31.txt |
AC |
1594 ms |
724 KB |
subtask_01_32.txt |
AC |
1592 ms |
720 KB |
subtask_01_33.txt |
AC |
1597 ms |
720 KB |
subtask_01_34.txt |
AC |
1581 ms |
732 KB |
subtask_01_35.txt |
AC |
1592 ms |
720 KB |
subtask_01_36.txt |
AC |
1586 ms |
724 KB |
subtask_01_37.txt |
AC |
1589 ms |
840 KB |
subtask_01_38.txt |
AC |
1591 ms |
848 KB |
subtask_01_39.txt |
AC |
1584 ms |
848 KB |
subtask_01_40.txt |
AC |
1591 ms |
716 KB |
subtask_01_41.txt |
AC |
1586 ms |
848 KB |
subtask_01_42.txt |
AC |
1591 ms |
848 KB |
subtask_01_43.txt |
AC |
1594 ms |
848 KB |
subtask_01_44.txt |
AC |
1596 ms |
720 KB |
subtask_01_45.txt |
AC |
1595 ms |
720 KB |
subtask_01_46.txt |
AC |
1596 ms |
716 KB |
subtask_01_47.txt |
AC |
1596 ms |
720 KB |
subtask_01_48.txt |
AC |
1591 ms |
720 KB |
subtask_01_49.txt |
AC |
1580 ms |
848 KB |
subtask_01_50.txt |
AC |
1596 ms |
848 KB |