RCO presents 日本橋ハーフマラソン 本戦

Submission #2176261

Source codeソースコード

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

const int N = 8;
int d, t;
int c[N];
int a[N];

bool reach[100];
bool cand[100];

unsigned long xor128(void) {
    static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned long t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

// [0, k)
int rand(int k) {
    return xor128() % k;
}

int bitcount(int bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

void fill(int i) {
    //cerr << "fill " << i << endl; cerr.flush();
    cout << "fill " << i << endl; cout.flush();
}

void move(int i, int j) {
    cout << "move " << i << " " << j << endl; cout.flush();
}

void change(int i) {
    //cerr << "change " << i << endl; cerr.flush();
    cout << "change " << i << endl; cout.flush();
}

void pass() {
    //cerr << "pass" << endl; cerr.flush();
    cout << "pass" << endl; cout.flush();
}

void sell(int i) {
    int n = bitcount(i);
    //cerr << "sell " << n; cerr.flush();
    cout << "sell " << n;
    for (int j = 0; j < N; j++) {
        if ((i>>j)&1)
            cout << " " << j+1;
    }
    cout << endl; cout.flush();
}

void calc() {
    memset(reach, false, sizeof(reach));
    reach[0] = true;
    for (int i = 0; i < N; i++) {
        if (c[i] == a[i]) {
            for (int j = 99; j >= 0; j--) {
                if (reach[j])
                    reach[j+c[i]] = true;
            }
        }
    }
}

void calc_cand() {
    memset(cand, false, sizeof(cand));
    cand[0] = true;
    for (int i = 0; i < N; i++) {
        for (int j = 99; j >= 0; j--) {
            if (cand[j])
                cand[j+c[i]] = true;
        }
    }
}

int calc_sell_tanks() {
    for (int i = 1; i < (1<<N); i++) {
        int sum = 0;
        for (int j = 0; j < N; j++) {
            if (((i>>j)&1) && a[j] == c[j])
                sum += c[j];
        }
        if (sum == d)
            return i;
    }
    return -1;
}

bool full() {
    for (int i = 0; i < N; i++) {
        if (a[i] != c[i])
            return false;
    }
    return true;
}

int countOver() {
    int res = 0;
    for (int i = 40; i <= 50; i++) {
        if (cand[i])
            res++;
    }
    return res;
}

int changeIdx() {
    vector<int> vec;
    for (int i = 0; i < N; i++) {
        if (c[i] < 9) {
            vec.push_back(i);
        }
    }
    int l = (int)vec.size();
    return vec[rand(l)];
}

int fillIdx() {
    int res = 0, maxi = 0;
    for (int i = 0; i < N; i++) {
        if (a[i] != c[i] && maxi < c[i]) {
            res = i;
            maxi = c[i];
        }
    }
    return res;
}

void think() {
    calc();
    calc_cand();
    int co = countOver();
    if (d >= 30 && reach[d]) {
        sell(calc_sell_tanks());
    } else if (co < 5) {
        int idx = changeIdx()+1;
        //cerr << "change?? " << idx << endl; cerr.flush();
        change(idx);
    } else if (!full()) {
        //cerr << "fill??" << endl; cerr.flush();
        fill(fillIdx()+1);
    } else {
        //cerr << "pass??" << endl; cerr.flush();
        pass();
    }
}

void input() {
    cin >> d >> t;
    for (int i = 0; i < N; i++) cin >> c[i];
    for (int i = 0; i < N; i++) cin >> a[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    for (int i = 0; i < 1000; i++) {
        input();
        think();
    }
}

Submission

Task問題 A - 石油王Xの憂鬱
User nameユーザ名 assy
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 5504684
Source lengthソースコード長 4828 Byte
File nameファイル名
Exec time実行時間 47 ms
Memory usageメモリ使用量 724 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 116508 / 417500 subtask_01_01.txt
test_02 110964 / 417500 subtask_01_02.txt
test_03 124180 / 417500 subtask_01_03.txt
test_04 111066 / 417500 subtask_01_04.txt
test_05 108167 / 417500 subtask_01_05.txt
test_06 109059 / 417500 subtask_01_06.txt
test_07 117300 / 417500 subtask_01_07.txt
test_08 116653 / 417500 subtask_01_08.txt
test_09 115466 / 417500 subtask_01_09.txt
test_10 126689 / 417500 subtask_01_10.txt
test_11 107911 / 417500 subtask_01_11.txt
test_12 105782 / 417500 subtask_01_12.txt
test_13 109802 / 417500 subtask_01_13.txt
test_14 99061 / 417500 subtask_01_14.txt
test_15 107318 / 417500 subtask_01_15.txt
test_16 108533 / 417500 subtask_01_16.txt
test_17 110246 / 417500 subtask_01_17.txt
test_18 93527 / 417500 subtask_01_18.txt
test_19 119501 / 417500 subtask_01_19.txt
test_20 100841 / 417500 subtask_01_20.txt
test_21 113692 / 417500 subtask_01_21.txt
test_22 106700 / 417500 subtask_01_22.txt
test_23 104345 / 417500 subtask_01_23.txt
test_24 106094 / 417500 subtask_01_24.txt
test_25 107796 / 417500 subtask_01_25.txt
test_26 106914 / 417500 subtask_01_26.txt
test_27 116359 / 417500 subtask_01_27.txt
test_28 120315 / 417500 subtask_01_28.txt
test_29 103111 / 417500 subtask_01_29.txt
test_30 112754 / 417500 subtask_01_30.txt
test_31 116689 / 417500 subtask_01_31.txt
test_32 106589 / 417500 subtask_01_32.txt
test_33 108744 / 417500 subtask_01_33.txt
test_34 104232 / 417500 subtask_01_34.txt
test_35 114393 / 417500 subtask_01_35.txt
test_36 112346 / 417500 subtask_01_36.txt
test_37 117249 / 417500 subtask_01_37.txt
test_38 115520 / 417500 subtask_01_38.txt
test_39 103407 / 417500 subtask_01_39.txt
test_40 101586 / 417500 subtask_01_40.txt
test_41 107288 / 417500 subtask_01_41.txt
test_42 106174 / 417500 subtask_01_42.txt
test_43 113383 / 417500 subtask_01_43.txt
test_44 111400 / 417500 subtask_01_44.txt
test_45 104042 / 417500 subtask_01_45.txt
test_46 113246 / 417500 subtask_01_46.txt
test_47 111949 / 417500 subtask_01_47.txt
test_48 101156 / 417500 subtask_01_48.txt
test_49 104804 / 417500 subtask_01_49.txt
test_50 113833 / 417500 subtask_01_50.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 45 ms 720 KB
subtask_01_02.txt AC 44 ms 720 KB
subtask_01_03.txt AC 45 ms 720 KB
subtask_01_04.txt AC 44 ms 592 KB
subtask_01_05.txt AC 46 ms 716 KB
subtask_01_06.txt AC 41 ms 724 KB
subtask_01_07.txt AC 43 ms 720 KB
subtask_01_08.txt AC 43 ms 720 KB
subtask_01_09.txt AC 44 ms 716 KB
subtask_01_10.txt AC 43 ms 724 KB
subtask_01_11.txt AC 44 ms 720 KB
subtask_01_12.txt AC 45 ms 720 KB
subtask_01_13.txt AC 43 ms 724 KB
subtask_01_14.txt AC 43 ms 716 KB
subtask_01_15.txt AC 44 ms 716 KB
subtask_01_16.txt AC 44 ms 628 KB
subtask_01_17.txt AC 45 ms 720 KB
subtask_01_18.txt AC 46 ms 720 KB
subtask_01_19.txt AC 47 ms 720 KB
subtask_01_20.txt AC 46 ms 720 KB
subtask_01_21.txt AC 47 ms 720 KB
subtask_01_22.txt AC 45 ms 720 KB
subtask_01_23.txt AC 43 ms 720 KB
subtask_01_24.txt AC 43 ms 720 KB
subtask_01_25.txt AC 46 ms 592 KB
subtask_01_26.txt AC 47 ms 720 KB
subtask_01_27.txt AC 44 ms 720 KB
subtask_01_28.txt AC 46 ms 716 KB
subtask_01_29.txt AC 45 ms 724 KB
subtask_01_30.txt AC 44 ms 716 KB
subtask_01_31.txt AC 42 ms 720 KB
subtask_01_32.txt AC 43 ms 720 KB
subtask_01_33.txt AC 45 ms 720 KB
subtask_01_34.txt AC 45 ms 596 KB
subtask_01_35.txt AC 46 ms 716 KB
subtask_01_36.txt AC 44 ms 592 KB
subtask_01_37.txt AC 45 ms 720 KB
subtask_01_38.txt AC 43 ms 720 KB
subtask_01_39.txt AC 42 ms 720 KB
subtask_01_40.txt AC 43 ms 724 KB
subtask_01_41.txt AC 45 ms 720 KB
subtask_01_42.txt AC 44 ms 720 KB
subtask_01_43.txt AC 44 ms 712 KB
subtask_01_44.txt AC 44 ms 720 KB
subtask_01_45.txt AC 45 ms 720 KB
subtask_01_46.txt AC 45 ms 720 KB
subtask_01_47.txt AC 45 ms 720 KB
subtask_01_48.txt AC 43 ms 720 KB
subtask_01_49.txt AC 42 ms 724 KB
subtask_01_50.txt AC 44 ms 720 KB