#892457 (C++14) No.5017 Tool-assisted Shooting

提出ソース

結果

問題	No.5017 Tool-assisted Shooting
ユーザー	よーちゃん
提出日時	2023-07-16 18:59:30
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	9,308 bytes
コンパイル時間	2,432 ms
コンパイル使用メモリ	154,532 KB
実行使用メモリ	28,028 KB
スコア	43,001
平均クエリ数	70.93
最終ジャッジ日時	2023-07-16 19:06:18
合計ジャッジ時間	119,954 ms
ジャッジサーバーID （参考情報）	judge9 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	803 ms 27,460 KB
testcase_01	RE	-
testcase_02	RE	-
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	TLE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	RE	-
testcase_12	AC	1,316 ms 27,488 KB
testcase_13	RE	-
testcase_14	AC	333 ms 27,560 KB
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	AC	905 ms 27,572 KB
testcase_18	AC	1,155 ms 27,380 KB
testcase_19	AC	816 ms 27,200 KB
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	AC	1,200 ms 27,684 KB
testcase_28	AC	348 ms 27,388 KB
testcase_29	TLE	-
testcase_30	TLE	-
testcase_31	TLE	-
testcase_32	TLE	-
testcase_33	TLE	-
testcase_34	TLE	-
testcase_35	AC	1,339 ms 27,660 KB
testcase_36	TLE	-
testcase_37	AC	1,316 ms 26,800 KB
testcase_38	RE	-
testcase_39	RE	-
testcase_40	RE	-
testcase_41	AC	1,611 ms 27,576 KB
testcase_42	TLE	-
testcase_43	RE	-
testcase_44	AC	1,016 ms 27,696 KB
testcase_45	RE	-
testcase_46	TLE	-
testcase_47	RE	-
testcase_48	AC	1,370 ms 26,848 KB
testcase_49	TLE	-
testcase_50	RE	-
testcase_51	RE	-
testcase_52	TLE	-
testcase_53	RE	-
testcase_54	AC	800 ms 27,048 KB
testcase_55	AC	1,209 ms 27,908 KB
testcase_56	TLE	-
testcase_57	RE	-
testcase_58	AC	1,012 ms 27,688 KB
testcase_59	RE	-
testcase_60	TLE	-
testcase_61	AC	694 ms 27,192 KB
testcase_62	RE	-
testcase_63	RE	-
testcase_64	TLE	-
testcase_65	TLE	-
testcase_66	RE	-
testcase_67	AC	1,413 ms 27,264 KB
testcase_68	RE	-
testcase_69	AC	499 ms 26,996 KB
testcase_70	TLE	-
testcase_71	TLE	-
testcase_72	RE	-
testcase_73	RE	-
testcase_74	RE	-
testcase_75	AC	901 ms 27,000 KB
testcase_76	TLE	-
testcase_77	RE	-
testcase_78	AC	869 ms 27,148 KB
testcase_79	RE	-
testcase_80	AC	896 ms 26,912 KB
testcase_81	AC	1,735 ms 26,516 KB
testcase_82	TLE	-
testcase_83	RE	-
testcase_84	TLE	-
testcase_85	AC	1,363 ms 27,176 KB
testcase_86	TLE	-
testcase_87	RE	-
testcase_88	RE	-
testcase_89	TLE	-
testcase_90	TLE	-
testcase_91	RE	-
testcase_92	TLE	-
testcase_93	AC	177 ms 26,920 KB
testcase_94	RE	-
testcase_95	AC	367 ms 26,936 KB
testcase_96	AC	165 ms 26,604 KB
testcase_97	RE	-
testcase_98	TLE	-
testcase_99	RE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>
#include <time.h>

#define InfL 2000000000
#define InfLL 4000000000000000000LL
#define mod 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;

bool debug = false; // false : 提出, true : fin - fout
double time_ratio = 1.0;
clock_t time_ini;
string file_No = "0000";
ifstream fin;
ofstream fout;
ofstream fout_debug;
int Gaussian_size = 1000000;
vector<double> Gaussian_(Gaussian_size);


constexpr int width = 25;  // フィールドの幅
constexpr int height = 60; // フィールドの高さ
constexpr int max_turn = 1000; // ゲームの最大ターン数

int xR(int x) {
	int ans = x + 1;
	ans %= 25;
	return ans;
}
int xL(int x) {
	int ans = x - 1;
	ans += 25;
	ans %= 25;
	return ans;
}

void debug_init() {
	string txt = ".txt";

	string ifname = "in\\";
	ifname = ifname + file_No + txt;
	fin.open(ifname);
	string ofname = "out\\";
	ofname = ofname + file_No + txt;
	fout.open(ofname);
	string ofname_debug = "debug\\";
	ofname_debug = ofname_debug + file_No + txt;
	fout_debug.open(ofname_debug);

	time_ratio = 0.133; // 5950X
	// time_ratio = 0.183; // 12700KF

}

void debug_end() {
	fin.close();
	fout.close();
	fout_debug.close();
}

double time_diff()
{
	ll time_tmp = clock();
	const double time = time_ratio * static_cast<double>(time_tmp - time_ini) / CLOCKS_PER_SEC * 1000.0;
	return time;
}

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

double RAND_() {
	while (1) {
		double rand_ = (double)(xor128() % InfL) / (double)InfL;
		if (rand_ >= 0 && rand_ < 1)
			return rand_;
	}
}

double Gaussian() {
	double X = RAND_();
	double Y = RAND_();
	double Z = sqrt(-2.0 * log(X)) * cos(2.0 * acos(-1.0) * Y);
	return Z;
}

struct Pi_est {
	vector<int> n;
	vector<double> P;
	int t = 0;
	void init() {
		n.resize(25, 0);
		P.resize(25, 0.045);
	}
	void re_est(vector<int> x) {
		t++;
		for (int xtmp : x)
			n[xtmp]++;
		rep(xtmp, 25) {
			P[xtmp] = (double)n[xtmp] / (double)t;
			P[xtmp] = max(0.01, P[xtmp]);
			P[xtmp] = min(0.08, P[xtmp]);
		}
		return;
	}
};

Pi_est pi_est;

struct Enemy {
	int h, p, x, y, hrem, id;
	void init(int h_, int p_, int x_, int id_) {
		h = h_;
		p = p_;
		x = x_;
		y = 59;
		id = id_;
		hrem = h_;
	}
};

struct Input {
	int n;
	vector<int> h, p, x;
	void readProblem(istream& in = cin) {
		in >> n;
		if (n == -1) return;
		h.resize(n);
		p.resize(n);
		x.resize(n);
		rep(i, n)
			in >> h[i] >> p[i] >> x[i];
		pi_est.re_est(x);
		return;
	}
};

struct Output {
	char ans = 'S';


	void resize_all() {

	}
	void writeSolution(ostream& out = cout) {
		out << ans << "\n";
		return;
	}
};

Input input[1000];
Output output[1000];

struct Field {
	int power = 100;
	int score = 0;
	int X = 12;
	int idtmp;
	bool stop = false;
	vector<Enemy> E;
	set<int> id_active;
	vector<vi> id_x;
	vector<vi> id_xy;
	void init() {
		id_x.resize(25);
		id_xy.resize(25, vi(60+10, -1));
	}
	void read(int t) {
		rep(x, 25) {
			rep(y, 60)
				id_xy[x][y] = -1;
		}
		set<int> id_erase;
		for (int id : id_active) {
			E[id].y--;
			if (E[id].y == -1) {
				id_erase.insert(id);
				id_x[E[id].x].erase(id_x[E[id].x].begin());
			}
			else {
				id_xy[E[id].x][E[id].y] = id;
				if (E[id].y == 0) {
					if (X == E[id].x)
						stop = true;
				}
			}
		}
		for (int id : id_erase)
			id_active.erase(id);
		rep (i, input[t].n) {
			Enemy e;
			e.init(input[t].h[i], input[t].p[i], input[t].x[i], idtmp);
			id_xy[input[t].x[i]][59] = idtmp;
			E.push_back(e);
			id_x[e.x].push_back(idtmp);
			id_active.insert(idtmp);
			idtmp++;
		}
	}
};

Field field;

struct Plan {
	int score = 0;
	int power = field.power;
	int X = 12;
	string ans;
	vector<int> to;
	void make_to() {
		vector<pii> bs;
		for (int id : field.id_active)
			bs.push_back(make_pair(field.E[id].y, id));
		sort(bs.begin(), bs.end());
		to.clear();
		for (pii b : bs) {
			to.push_back(b.second);
		}
	}
	void re_to() {
		int S = to.size();
		set<int> id_ex;
		rrep(i, S) {
			id_ex.insert(to[i]);
			if (field.id_active.find(to[i]) == field.id_active.end())
				to.erase(to.begin() + i);
		}
		for (int id : field.id_active) {
			if (id_ex.find(id) == id_ex.end())
				to.push_back(id);
		}
	}
	void make_ans() {
		ans = "";
		vector<Enemy> E = field.E;
		vector<vi> id_x = field.id_x;
		int x = X;
		int t = 0;
		int k = 0;
		score = 0;
		power = field.power;
		set<int> bset;
		bset.insert(-1);
		while (1) {
			if (k >= to.size()) break;
			if (field.id_xy[x][t] != -1) {
				score = -1;
				break;
			}
			int id = to[k];
			int xto = field.E[id].x;
			int len = (xto - x + 25) % 25;
			if (len > 12)
				len -= 25;
			int tnext = t + abs(len);
			if (field.E[id].y - tnext <= 0) {
				k++;
				continue;
			}
			if (len > 0) {
				int xnext = xR(x);
				if (bset.find(field.id_xy[xnext][t]) == bset.end() || bset.find(field.id_xy[xnext][t + 1]) == bset.end())
					ans.push_back('S');
				else {
					ans.push_back('R');
					x = xnext;
				}
			}
			else if (len < 0) {
				int xnext = xL(x);
				if (bset.find(field.id_xy[xnext][t]) == bset.end() || bset.find(field.id_xy[xnext][t + 1]) == bset.end())
					ans.push_back('S');
				else {
					ans.push_back('L');
					x = xnext;
				}
			}
			else
				ans.push_back('S');
			int s = id_x[x].size();
			if (s > 0) {
				int idtmp = id_x[x][0];
				int hrem = E[idtmp].hrem;
				E[idtmp].hrem -= power / 100;
				if (hrem <= 0) {
					power += E[idtmp].p;
					score += E[idtmp].h;
					id_x[x].erase(id_x[x].begin());
					bset.insert(idtmp);
					if (id == idtmp)
						k++;
				}
			}
			t++;
			if (t >= 60) break;
		}
	}
};

Plan plan;

void solve_init() {
	rep(t, 1000)
		output[t].resize_all();
	field.init();
	return;
}

void solveA(int t) {
	field.read(t);
	if (field.stop) return;

	return;
}

void solveB(int t) {
	char ans = 'S';
	plan.re_to();
	plan.make_ans();
	ll sc1 = plan.score;
	ll sc2 = plan.power;
	ll le = plan.ans.length();
	ll sc = sc1 * 100000 + sc2 * 100000 + plan.ans.length();



	double start_temp = 0.0;
	double end_temp = 0.0;
	double TIME_LIMIT = 1.95 * t;
	ll loop_count = 0;
	double time_now = 0.0;
	double temp = 0.0;

	int S = plan.to.size();
	while (1) {
		//break;
		if (loop_count % 1000 == 0) {
			time_now = time_diff();
			if (time_now > TIME_LIMIT)
			//if(loop_count == 1000)
				break;
			temp = start_temp + (end_temp - start_temp) * time_now / TIME_LIMIT;
		}

		loop_count++;
		ll scdiff = 0;

		int i = xor128() % S;
		int j = xor128() % S;
		vi to_old = plan.to;

		int type = xor128() % 1;
		if (type == 0) {
			if (i == j) continue;
			swap(plan.to[i], plan.to[j]);
		}
		else if (type == 1) {
			vector<pii> torand(S);
			rep(s, S)
				torand[s] = make_pair(xor128(), plan.to[s]);
			sort(torand.begin(), torand.end());
			rep(s, S)
				plan.to[s] = torand[s].second;
		}
		rep(x, 25) {
			vector<pii> ss;
			vi slist;
			rep(s, S) {
				if (field.E[plan.to[s]].x != x) continue;
				slist.push_back(s);
				ss.push_back(make_pair(field.E[plan.to[s]].y, plan.to[s]));
			}
			sort(ss.begin(), ss.end());
			int P = slist.size();
			rep(p, P) {
				plan.to[slist[p]] = ss[p].second;
			}
		}


		plan.make_ans();
		ll scnew1 = plan.score;
		ll scnew2 = plan.power;

		scdiff = scnew1 * 100000 + scnew2 * 100000 + plan.ans.length() - sc;

		//cout << plan.ans.length() << endl;
		double prob = exp(scdiff / temp);
		//if (scdiff > 0) {
		bool d = false;
		if (scnew1 >= 0) {
			if (prob > RAND_())
				d = true;
		}
		else {
			if (prob > RAND_())
				d = true;
		}
		if (d) {
			sc += scdiff;
		}
		else
			plan.to = to_old;

	}

	plan.make_ans();
	ans = plan.ans[0];


	if (ans == 'R') {
		field.X = xR(field.X);
		plan.X = xR(plan.X);
	}
	if (ans == 'L') {
		field.X = xL(field.X);
		plan.X = xL(plan.X);
	}
	int s = field.id_x[field.X].size();
	if (s > 0) {
		int id = field.id_x[field.X][0];
		field.E[id].hrem -= field.power / 100;
		if (field.E[id].hrem <= 0) {
			field.id_x[field.X].erase(field.id_x[field.X].begin());
			int y = field.E[id].y;
			field.id_xy[field.X][y] = -1;
			field.power += field.E[id].p;
			field.score += field.E[id].h;
			field.id_active.erase(id);
		}
	}

	output[t].ans = ans;


	return;
}

int main(int argc, char* argv[]) {
	if (argc >= 2) file_No = argv[1];
	time_ini = clock();
	if (debug)
		debug_init();
	pi_est.init();
	solve_init();
	plan.make_to();
	rep(t, 1000) {
		debug ? input[t].readProblem(fin) : input[t].readProblem();
		solveA(t);
		if (field.stop) return 0;
		solveB(t);
		debug ? output[t].writeSolution(fout) : output[t].writeSolution();
	}
	fout_debug << field.score << endl;
	if (debug)
		debug_end();
	return 0;
}

yukicoder

結果

テストケース

ソースコード