Submission #2176261
Source Code Expand
#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 Info
Submission Time | |
---|---|
Task | A - 石油王Xの憂鬱 |
User | assy |
Language | C++14 (GCC 5.4.1) |
Score | 5504684 |
Code Size | 4828 Byte |
Status | AC |
Exec Time | 47 ms |
Memory | 724 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 | 116508 / 417500 | 110964 / 417500 | 124180 / 417500 | 111066 / 417500 | 108167 / 417500 | 109059 / 417500 | 117300 / 417500 | 116653 / 417500 | 115466 / 417500 | 126689 / 417500 | 107911 / 417500 | 105782 / 417500 | 109802 / 417500 | 99061 / 417500 | 107318 / 417500 | 108533 / 417500 | 110246 / 417500 | 93527 / 417500 | 119501 / 417500 | 100841 / 417500 | 113692 / 417500 | 106700 / 417500 | 104345 / 417500 | 106094 / 417500 | 107796 / 417500 | 106914 / 417500 | 116359 / 417500 | 120315 / 417500 | 103111 / 417500 | 112754 / 417500 | 116689 / 417500 | 106589 / 417500 | 108744 / 417500 | 104232 / 417500 | 114393 / 417500 | 112346 / 417500 | 117249 / 417500 | 115520 / 417500 | 103407 / 417500 | 101586 / 417500 | 107288 / 417500 | 106174 / 417500 | 113383 / 417500 | 111400 / 417500 | 104042 / 417500 | 113246 / 417500 | 111949 / 417500 | 101156 / 417500 | 104804 / 417500 | 113833 / 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 | 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 |