結果

問題 No.5020 Averaging
ユーザー A8pf
提出日時 2024-02-25 15:19:34
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 587 ms / 1,000 ms
コード長 5,332 bytes
コンパイル時間 2,904 ms
コンパイル使用メモリ 232,336 KB
実行使用メモリ 16,700 KB
スコア 16,377,294
最終ジャッジ日時 2024-02-25 15:20:13
合計ジャッジ時間 31,418 ms
ジャッジサーバーID
(参考情報)
judge13 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
// 128bit
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
__int128 parse(string &s) {
__int128 ret = 0;
for (int i = 0; i < s.length(); i++)
if ('0' <= s[i] && s[i] <= '9')
ret = 10 * ret + s[i] - '0';
return ret;
}
// 128bit
constexpr int MAX_TURN = 50;
constexpr __int128 TARGET = 500000000000000000;
struct Card {
__int128 omote, ura;
};
class GameState
{
private:
int _turn;
vector<Card> _cards;
vector<pair<int, int>> _commandHistory;
public:
int nowScore;
pair<int, int> first_action_;
GameState(){};
GameState(vector<unsigned long long> omotes, vector<unsigned long long> uras): _turn(0), nowScore(0) {
for (int i = 0; i < omotes.size(); i++) {
_cards.push_back({omotes[i], uras[i]});
}
}
__int128 getEstimatedScore() {
__int128 score = 0;
// 1
__int128 omotediff = TARGET - _cards[0].omote;
if (omotediff > 0) {
omotediff *= -1;
}
score += omotediff;
__int128 uradiff = TARGET - _cards[0].ura;
if (uradiff > 0) {
uradiff *= -1;
}
score += uradiff;
//
if (omotediff == 0 && uradiff == 0) {
score += 9999999999999999;
}
// 2
const Card OTHER_TARGET = { TARGET * 2 - _cards[0].omote, TARGET * 2 - _cards[0].ura };
for (int i = 1; i < _cards.size(); i++) {
__int128 omotediff = OTHER_TARGET.omote - _cards[i].omote;
if (omotediff > 0) {
omotediff *= -1;
}
score += omotediff * _turn;
__int128 uradiff = OTHER_TARGET.ura - _cards[i].ura;
if (uradiff > 0) {
uradiff *= -1;
}
score += uradiff * _turn;
//
if (omotediff == 0 && uradiff == 0) {
score += 99999999;
}
}
return score;
}
// 1
void advance(int u, int v)
{
_commandHistory.push_back({u, v});
_turn++;
Card newCard = {(_cards[u].omote + _cards[v].omote) / 2, (_cards[u].ura + _cards[v].ura) / 2};
_cards[u] = newCard;
_cards[v] = newCard;
nowScore = getEstimatedScore();
}
//
vector<pair<int, int>> legalActions() const
{
vector<pair<int, int>> ret;
for (int i = 0; i < _cards.size(); i++) {
for (int j = i + 1; j < _cards.size(); j++) {
ret.push_back({i, j});
}
}
return ret;
}
//
bool isDone() const
{
return _turn == MAX_TURN;
}
//
string outputCommand() {
stringstream ss;
ss << _commandHistory.size() << endl;
for (auto command : _commandHistory) {
ss << command.first + 1 << " " << command.second + 1 << endl;
}
return ss.str();
}
//
double getScore() {
ull v = max( max((ull)_cards[0].omote, (ull)TARGET) - min((ull)_cards[0].omote, (ull)TARGET), max((ull)_cards[0].ura, (ull)TARGET) - min((ull
        )_cards[0].ura, (ull)TARGET) );
long long score = 2000000 - 100000 * log10(static_cast<long double>(v));
return score;
}
};
bool operator<(const GameState &state1, const GameState &state2)
{
return state1.nowScore < state2.nowScore;
}
pair<int,int> beamSearchAction(const GameState &initState, const int beamWidth, const int beamDepth)
{
priority_queue<GameState> nowBeam;
GameState bestState;
nowBeam.push(initState);
for (int t = 0; t < beamDepth; t++)
{
std::priority_queue<GameState> nextBeam;
for (int i = 0; i < beamWidth; i++)
{
if (nowBeam.empty())
break;
GameState nowState = nowBeam.top();
nowBeam.pop();
auto legal_actions = nowState.legalActions();
for (const auto &action : legal_actions)
{
GameState nextState = nowState;
nextState.advance(action.first, action.second);
if (t == 0)
nextState.first_action_ = action;
nextBeam.push(nextState);
}
}
nowBeam = nextBeam;
bestState = nowBeam.top();
if (bestState.isDone())
{
break;
}
}
return bestState.first_action_;
}
pair<vector<unsigned long long>, vector<unsigned long long>> getFromInput() {
int n;
cin >> n;
vector<unsigned long long> omotes(n), uras(n);
for (int i = 0; i < n; i++) {
cin >> omotes[i] >> uras[i];
}
return {omotes, uras};
}
int main() {
//
auto input = getFromInput();
GameState state(input.first, input.second);
while (!state.isDone()) {
auto action = beamSearchAction(state, 3, 3);
state.advance(action.first, action.second);
// cerr<<state.getScore()<<endl;
}
cout << state.outputCommand();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0