提出 #63889785
ソースコード 拡げる
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
// 答えのクラス
struct Answer {
int a[100];
int b[100];
};
// スコア計算のための関数
int get_actual_score(int N, int K, vector<int> T, Answer ans) {
for (int i = 0; i < N; i++) {
if (ans.a[i] < 0 || ans.a[i] >= N) return 0;
if (ans.b[i] < 0 || ans.b[i] >= N) return 0;
}
// シミュレーション
vector<int> Count(N, 0);
int pos = 0;
for (int steps = 1; steps <= K; steps++) {
Count[pos] += 1;
pos = (Count[pos] % 2 == 1 ? ans.a[pos] : ans.b[pos]);
}
int error = 0;
for (int i = 0; i < N; i++) error += abs(T[i] - Count[i]);
// 出力
return 2 * K - error;
}
// =============================================================================================================
// === 1. クラス等の準備
// =============================================================================================================
const int NUM_CANDIDATES = 5;
const int NUM_SEARCHES = 4000;
const int WIDTH_MIN = 100;
const int WIDTH_MAX = 500;
const int FINAL_SEARCH = 100;
// 乱数
int Param;
unsigned int seed = 869120;
unsigned int Rand() { seed ^= seed << 13; seed ^= seed >> 17; seed ^= seed << 5; return seed; }
// 操作のクラス
struct Operation {
vector<int> c;
int add_cost;
int new_diff;
};
// ビームの状態のクラス
struct State {
int score;
int used_diff;
int use_count;
int prv;
Operation op;
vector<unsigned long long> used;
};
// 操作の比較関数
bool operator<(const Operation& a1, const Operation& a2) {
if (a1.add_cost + abs(a1.new_diff) < a2.add_cost + abs(a2.new_diff)) return true;
return false;
}
// 状態の比較関数
bool operator<(const State& a1, const State& a2) {
int score1 = a1.score + abs(a1.used_diff) + 10 * a1.use_count;
int score2 = a2.score + abs(a2.used_diff) + 10 * a2.use_count;
if (score1 < score2) return true;
return false;
}
// 最初の状態を返す関数
State first_state(int N) {
State S;
S.score = 0;
S.used_diff = 0;
S.use_count = 0;
S.prv = -1;
S.op = Operation{ vector<int>{}, 0, 0 };
S.used = vector<unsigned long long>(4, 0);
return S;
}
// =============================================================================================================
// === 2. 前計算を行う関数
// =============================================================================================================
void precount(int N, vector<int> cost, vector<vector<vector<Operation>>>& cand) {
// 1 個の場合
for (int i = 0; i < 2 * N; i++) {
cand[1][cost[i]].emplace_back(Operation{ vector<int>{i}, 0, 0 });
}
// 2 個の場合
for (int i = 0; i < 2 * N; i++) {
for (int j = i + 1; j < 2 * N; j++) {
if (j - i == N) continue;
if (cost[i] + cost[j] > 10100) continue;
cand[2][cost[i] + cost[j]].emplace_back(Operation{ vector<int>{i, j}, 0, 0 });
}
}
// 3 個の場合
for (int i = 0; i < 2 * N; i++) {
for (int j = i + 1; j < 2 * N; j++) {
for (int k = j + 1; k < 2 * N; k++) {
if (j - i == N) continue;
if (k - i == N) continue;
if (k - j == N) continue;
if (cost[i] + cost[j] + cost[k] > 10100) continue;
cand[3][cost[i] + cost[j] + cost[k]].emplace_back(Operation{ vector<int>{i, j, k}, 0, 0 });
}
}
}
}
// =============================================================================================================
// === 3. 復元を行う関数
// =============================================================================================================
// 最終的な答えの復元
Answer reconstruct_final(int N, int cx, int cy, vector<int>& T, vector<vector<State>>& beam) {
Answer r;
for (int i = 0; i < N; i++) r.a[i] = -1;
for (int i = 0; i < N; i++) r.b[i] = -1;
for (int i = cx; i >= 1; i--) {
vector<int> idx_list = beam[i][cy].op.c;
for (int idx : idx_list) {
if (idx < N) r.a[idx] = i - 1;
if (idx >= N) r.b[idx - N] = i - 1;
}
cy = beam[i][cy].prv;
}
return r;
}
// ビンのコストの復元
vector<int> reconstruct_bins(int N, int cx, int cy, vector<int>& T, vector<vector<State>>& beam) {
vector<int> bin_sum(cx, 0);
for (int i = cx; i >= 1; i--) {
int nex = beam[i][cy].prv;
int diff = beam[i][cy].used_diff - beam[i - 1][nex].used_diff;
bin_sum[i - 1] = T[i - 1] + diff;
cy = nex;
}
return bin_sum;
}
// =============================================================================================================
// === 4-0. 答えの候補についてスコアを計算
// =============================================================================================================
Operation get_op(int N, vector<int> selection, vector<int>& cost, vector<int>& actual, int target, int used_diff, double remain_mul) {
Operation op;
op.c = selection;
op.add_cost = -target;
op.new_diff = used_diff - target;
for (int idx : selection) {
int wage = cost[idx];
if (idx % N < actual.size()) wage = (idx < N ? (actual[idx] + 1) / 2 : (actual[idx - N] + 0) / 2);
else wage = (int)(1.0 * wage * remain_mul + 0.5);
op.add_cost += wage;
op.new_diff += cost[idx];
}
op.add_cost = abs(op.add_cost);
return op;
}
// =============================================================================================================
// === 4-1. 答えの候補を得る関数 (前処理)
// =============================================================================================================
vector<Operation> enumerate_operation_range(int N, int cx, int cy, int select, vector<int>& T, vector<int>& cost, vector<int>& actual, double remain_mul, vector<vector<State>>& beam, vector<vector<vector<Operation>>>& cand) {
// 何も選ばない場合
if (select == 0) {
return vector<Operation>{Operation{ vector<int>{}, T[cx], beam[cx][cy].used_diff }};
}
vector<Operation> ret;
int target = T[cx];
// コストが実質ゼロのものを追加
for (int i = 0; i <= abs(beam[cx][cy].used_diff); i++) {
int val = target + (beam[cx][cy].used_diff >= 0 ? -i : +i);
if (val < 0 || val >= 10100) continue;
// 追加メイン
for (Operation r : cand[select][val]) {
bool flag = true;
for (int idx : r.c) {
if (((beam[cx][cy].used[idx >> 6] >> (idx & 63)) & 1) == 1) flag = false;
if (idx == cx || idx == cx + N) flag = false;
if (idx >= N && ((beam[cx][cy].used[(idx - N) >> 6] >> ((idx - N) & 63)) & 1) == 0) flag = false;
}
if (flag == false) continue;
ret.emplace_back(get_op(N, r.c, cost, actual, target, beam[cx][cy].used_diff, remain_mul));
if (ret.size() == NUM_CANDIDATES) return ret;
}
}
// それ以外のものを追加
for (int diff = 1; diff <= 200; diff++) {
for (int turn = 1; turn <= 2; turn++) {
int val = target;
if (turn == 1) val = target + (beam[cx][cy].used_diff >= 0 ? diff : -diff);
if (turn == 2) val = target - beam[cx][cy].used_diff - (beam[cx][cy].used_diff >= 0 ? diff : -diff);
if (val < 0 || val >= 10100) continue;
// 追加メイン
for (Operation r : cand[select][val]) {
bool flag = true;
for (int idx : r.c) {
if (((beam[cx][cy].used[idx >> 6] >> (idx & 63)) & 1) == 1) flag = false;
if (idx == cx || idx == cx + N) flag = false;
if (idx >= N && ((beam[cx][cy].used[(idx - N) >> 6] >> ((idx - N) & 63)) & 1) == 0) flag = false;
}
if (flag == false) continue;
ret.emplace_back(get_op(N, r.c, cost, actual, target, beam[cx][cy].used_diff, remain_mul));
if (ret.size() == NUM_CANDIDATES) return ret;
}
}
}
return ret;
}
// =============================================================================================================
// === 4-2. 答えの候補を得る関数 (3 個)
// =============================================================================================================
vector<Operation> enumerate_operation_three(int N, int cx, int cy, int select, vector<int>& T, vector<int>& cost, vector<int>& actual, double remain_mul, vector<vector<State>>& beam, vector<vector<vector<Operation>>>& cand) {
vector<int> unused_list;
for (int i = 0; i < 2 * N; i++) {
if (((beam[cx][cy].used[i >> 6] >> (i & 63)) & 1) == 0) unused_list.emplace_back(i);
}
vector<Operation> answer(NUM_CANDIDATES + 1);
for (int i = 0; i < answer.size(); i++) answer[i] = Operation{ vector<int>{}, 100000, 0 };
int target = T[cx];
// 更新処理
auto update = [&](Operation op) -> void {
answer[NUM_CANDIDATES] = op;
for (int i = NUM_CANDIDATES; i >= 1; i--) {
if (answer[i] < answer[i - 1]) swap(answer[i], answer[i - 1]);
else break;
}
};
// 候補を列挙: 通り数が少ない場合
int ways = ((int)unused_list.size()) * ((int)unused_list.size() - 1) * ((int)unused_list.size() - 2) / 6;
vector<vector<int>> search_ways;
if (ways <= NUM_SEARCHES) {
search_ways.resize(ways); int cnt = 0;
for (int i = 0; i < unused_list.size(); i++) {
for (int j = i + 1; j < unused_list.size(); j++) {
for (int k = j + 1; k < unused_list.size(); k++) {
int idx1 = unused_list[i];
int idx2 = unused_list[j];
int idx3 = unused_list[k];
search_ways[cnt] = vector<int>{ idx1, idx2, idx3 };
cnt += 1;
}
}
}
}
// 候補を列挙: 通り数が多い場合
else {
map<int, bool> Map;
search_ways.resize(NUM_SEARCHES / 3);
for (int loops = 0; loops < NUM_SEARCHES / 3; loops++) {
int c[3];
while (true) {
c[0] = unused_list[Rand() % unused_list.size()];
c[1] = unused_list[Rand() % unused_list.size()];
c[2] = unused_list[Rand() % unused_list.size()];
sort(c, c + 3);
int mask = (c[0] << 0) + (c[1] << 8) + (c[2] << 16);
if (Map[mask] == true) continue;
Map[mask] = true;
break;
}
search_ways[loops] = vector<int>{ c[0], c[1], c[2] };
}
}
// 候補について計算
for (vector<int> way : search_ways) {
if (abs(way[1] - way[0]) == 0 || abs(way[1] - way[0]) == N) continue;
if (abs(way[2] - way[0]) == 0 || abs(way[2] - way[0]) == N) continue;
if (abs(way[2] - way[1]) == 0 || abs(way[2] - way[1]) == N) continue;
if (abs(cx - way[0]) == 0 || abs(cx - way[0]) == N) continue;
if (abs(cx - way[1]) == 0 || abs(cx - way[1]) == N) continue;
if (abs(cx - way[2]) == 0 || abs(cx - way[2]) == N) continue;
Operation op = get_op(N, way, cost, actual, target, beam[cx][cy].used_diff, remain_mul);
update(op);
}
// 答えを返す
while (answer.size() >= 1) {
if (answer[answer.size() - 1].add_cost > 10000) answer.pop_back();
else break;
}
return answer;
}
// =============================================================================================================
// === 4-3. 答えの候補を得る関数 (4 個)
// =============================================================================================================
vector<Operation> enumerate_operation_four(int N, int cx, int cy, int select, vector<int>& T, vector<int>& cost, vector<int>& actual, double remain_mul, vector<vector<State>>& beam, vector<vector<vector<Operation>>>& cand) {
vector<int> unused_list;
for (int i = 0; i < 2 * N; i++) {
if (((beam[cx][cy].used[i >> 6] >> (i & 63)) & 1) == 0) unused_list.emplace_back(i);
}
vector<Operation> answer(NUM_CANDIDATES + 1);
for (int i = 0; i < answer.size(); i++) answer[i] = Operation{ vector<int>{}, 100000, 0 };
int target = T[cx];
// 更新処理
auto update = [&](Operation op) -> void {
answer[NUM_CANDIDATES] = op;
for (int i = NUM_CANDIDATES; i >= 1; i--) {
if (answer[i] < answer[i - 1]) swap(answer[i], answer[i - 1]);
else break;
}
};
// 候補を列挙: 通り数が少ない場合
int ways = ((int)unused_list.size()) * ((int)unused_list.size() - 1) * ((int)unused_list.size() - 2) * ((int)unused_list.size() - 3) / 24;
vector<vector<int>> search_ways;
if (ways <= NUM_SEARCHES) {
search_ways.resize(ways); int cnt = 0;
for (int i = 0; i < unused_list.size(); i++) {
for (int j = i + 1; j < unused_list.size(); j++) {
for (int k = j + 1; k < unused_list.size(); k++) {
for (int l = k + 1; l < unused_list.size(); l++) {
int idx1 = unused_list[i];
int idx2 = unused_list[j];
int idx3 = unused_list[k];
int idx4 = unused_list[l];
search_ways[cnt] = vector<int>{ idx1, idx2, idx3, idx4 };
cnt += 1;
}
}
}
}
}
// 候補を列挙: 通り数が多い場合
else {
map<int, bool> Map;
search_ways.resize(NUM_SEARCHES / 3);
for (int loops = 0; loops < NUM_SEARCHES / 3; loops++) {
int c[4];
while (true) {
c[0] = unused_list[Rand() % unused_list.size()];
c[1] = unused_list[Rand() % unused_list.size()];
c[2] = unused_list[Rand() % unused_list.size()];
c[3] = unused_list[Rand() % unused_list.size()];
sort(c, c + 4);
int mask = (c[0] << 0) + (c[1] << 8) + (c[2] << 16) + (c[3] << 24);
if (Map[mask] == true) continue;
Map[mask] = true;
break;
}
search_ways[loops] = vector<int>{ c[0], c[1], c[2], c[3] };
}
}
// 候補について計算
for (vector<int> way : search_ways) {
if (abs(way[1] - way[0]) == 0 || abs(way[1] - way[0]) == N) continue;
if (abs(way[2] - way[0]) == 0 || abs(way[2] - way[0]) == N) continue;
if (abs(way[2] - way[1]) == 0 || abs(way[2] - way[1]) == N) continue;
if (abs(way[3] - way[0]) == 0 || abs(way[3] - way[0]) == N) continue;
if (abs(way[3] - way[1]) == 0 || abs(way[3] - way[1]) == N) continue;
if (abs(way[3] - way[2]) == 0 || abs(way[3] - way[2]) == N) continue;
if (abs(cx - way[0]) == 0 || abs(cx - way[0]) == N) continue;
if (abs(cx - way[1]) == 0 || abs(cx - way[1]) == N) continue;
if (abs(cx - way[2]) == 0 || abs(cx - way[2]) == N) continue;
if (abs(cx - way[3]) == 0 || abs(cx - way[3]) == N) continue;
Operation op = get_op(N, way, cost, actual, target, beam[cx][cy].used_diff, remain_mul);
update(op);
}
// 答えを返す
while (answer.size() >= 1) {
if (answer[answer.size() - 1].add_cost > 10000) answer.pop_back();
else break;
}
return answer;
}
// =============================================================================================================
// === 5. 答えの候補を得る関数 (全体)
// =============================================================================================================
vector<Operation> enumerate_operation_all(int N, int cx, int cy, int select, vector<int>& T, vector<int>& cost, vector<vector<State>>& beam, vector<vector<vector<Operation>>>& cand) {
vector<int> actual = reconstruct_bins(N, cx, cy, T, beam);
int remain1 = 500000, remain2 = 500000;
double remain_mul = 0.0;
for (int i = 0; i < cx; i++) remain1 -= actual[i];
for (int i = 0; i < cx; i++) remain2 -= T[i];
remain_mul = 1.0 * remain1 / remain2;
if (select <= 3 && (select <= 2 || cx < 85)) {
return enumerate_operation_range(N, cx, cy, select, T, cost, actual, remain_mul, beam, cand);
}
else if (select == 3) {
return enumerate_operation_three(N, cx, cy, select, T, cost, actual, remain_mul, beam, cand);
}
else {
return enumerate_operation_four(N, cx, cy, select, T, cost, actual, remain_mul, beam, cand);
}
}
// =============================================================================================================
// === 6. チェック機構
// =============================================================================================================
bool checker(int N, int steps, Answer ans) {
vector<vector<int>> G(steps + 1);
for (int i = 0; i < N; i++) {
if (ans.a[i] != -1 && ans.a[i] <= steps) G[ans.a[i]].push_back(i);
if (ans.b[i] != -1 && ans.b[i] <= steps) G[ans.b[i]].push_back(i);
}
for (int i = 0; i <= steps; i++) {
if (G[i].size() == 0) continue;
vector<bool> used(N, false);
queue<int> Q; Q.push(i); used[i] = true;
while (!Q.empty()) {
int pos = Q.front(); Q.pop();
for (int to : G[pos]) {
if (used[to] == true) continue;
if (to <= steps) Q.push(to);
used[to] = true;
}
}
for (int j = steps + 1; j < N; j++) {
if (used[j] == true) return true;
}
return false;
}
return true;
}
// =============================================================================================================
// === 7. 問題を解く関数
// =============================================================================================================
pair<int, Answer> solver_main(int N, int L, vector<int> T, vector<int>& cost, vector<vector<vector<Operation>>>& cand, int mode, double timer) {
vector<vector<State>> beam(N + 1);
beam[0].push_back(first_state(N));
// ビームサーチ
for (int steps = 0; steps < N; steps++) {
int WIDTH = 1.0 * timer * max(WIDTH_MIN, (int)(WIDTH_MAX / pow(1.0 * (N - steps), 0.8)));
vector<State> next_beam;
// 計算開始
for (int i = 0; i < beam[steps].size(); i++) {
int lw = 1, rw = 2; if (mode == 2) lw = 0;
// 個数の範囲 [lw, rw] を決める
if (steps >= 5) { lw = 1; rw = 2; }
if (steps >= 40) { lw = 2; rw = 2; }
if (steps >= 70) { lw = 2; rw = 3; }
if (steps >= 90) { lw = 2; rw = 4; }
int remain = 2 * N - beam[steps][i].use_count;
int remain_need = (steps >= 90 ? 4 * (N - steps - 1) : 40 + 3 * (89 - steps));
lw = max(lw, remain - remain_need);
// 探索
for (int select = lw; select <= rw; select++) {
vector<Operation> ret = enumerate_operation_all(N, steps, i, select, T, cost, beam, cand);
for (Operation op : ret) {
State next_state = beam[steps][i];
next_state.op = op;
next_state.use_count += op.c.size();
next_state.used_diff = op.new_diff;
next_state.score += op.add_cost;
next_state.prv = i;
for (int idx : op.c) next_state.used[idx >> 6] += (1ULL << (idx & 63));
next_beam.push_back(next_state);
}
}
}
sort(next_beam.begin(), next_beam.end());
// 次のビームを計算
map<unsigned long long, bool> Map;
for (State s : next_beam) {
unsigned long long hashval = s.used[0] + 998244353LL * s.used[1] + 924844033LL * s.used[2] + 1000000007LL * s.used[3];
if (steps < 98 && Map[hashval] == true) continue;
if (steps < 25) {
Answer ans = reconstruct_final(N, steps, s.prv, T, beam);
for (int idx : s.op.c) {
if (idx < N) ans.a[idx] = steps;
else ans.b[idx - N] = steps;
}
if (checker(N, steps, ans) == false) continue;
}
Map[hashval] = true;
beam[steps + 1].emplace_back(s);
if (beam[steps + 1].size() == WIDTH) break;
}
}
// 答えの復元
int max_score = -1;
Answer final_ans;
for (int i = 0; i < FINAL_SEARCH; i++) {
if (i >= beam[N].size()) continue;
Answer cand_ans = reconstruct_final(N, N, i, T, beam);
int cand_score = get_actual_score(N, L, T, cand_ans);
if (max_score < cand_score) {
max_score = cand_score;
final_ans = cand_ans;
}
}
return make_pair(max_score, final_ans);
}
// =============================================================================================================
// === 7. 最初に呼び出される関数
// =============================================================================================================
Answer solver(int N, int L, vector<int> T) {
double start_time = 1.0 * clock() / CLOCKS_PER_SEC;
// 前準備 (1)
vector<pair<int, int>> sorted;
for (int i = 0; i < N; i++) sorted.push_back(make_pair(T[i], i));
sort(sorted.begin(), sorted.end());
sort(T.begin(), T.end());
// 前準備 (2)
vector<int> cost;
for (int i = 0; i < N; i++) cost.push_back((T[i] + 1) / 2);
for (int i = 0; i < N; i++) cost.push_back((T[i] + 0) / 2);
vector<vector<vector<Operation>>> cand(4, vector<vector<Operation>>(10102));
precount(N, cost, cand);
double p1_time = 1.0 * clock() / CLOCKS_PER_SEC - start_time;
// 計算 (1): 0 個を許さない
pair<int, Answer> r1 = solver_main(N, L, T, cost, cand, 1, 1.00);
double p2_time = 1.0 * clock() / CLOCKS_PER_SEC - start_time;
// 計算 (2): 0 個を許す
double timer = (1.6 - p1_time) / (p2_time - p1_time); timer -= 1.00;
timer = max(0.05, min(1.00, timer)); cerr << timer << endl;
pair<int, Answer> r2 = solver_main(N, L, T, cost, cand, 2, timer);
// 最終的な答えの計算
Answer pre_ans = (r1.first > r2.first ? r1.second : r2.second);
Answer ans;
for (int i = 0; i < N; i++) ans.a[sorted[i].second] = sorted[pre_ans.a[i]].second;
for (int i = 0; i < N; i++) ans.b[sorted[i].second] = sorted[pre_ans.b[i]].second;
return ans;
}
// =============================================================================================================
// === 8. メイン関数
// =============================================================================================================
int main() {
int N, L; cin >> N >> L;
vector<int> T(N, 0);
for (int i = 0; i < N; i++) cin >> T[i];
Answer ans = solver(N, L, T);
for (int i = 0; i < N; i++) cout << ans.a[i] << " " << ans.b[i] << endl;
cerr << "score = " << get_actual_score(N, L, T, ans) << endl;
return 0;
}
提出情報
| 提出日時 |
|
| 問題 |
A - Cleaning Up |
| ユーザ |
E869120 |
| 言語 |
C++ 20 (gcc 12.2) |
| 得点 |
149929536 |
| コード長 |
21515 Byte |
| 結果 |
AC |
| 実行時間 |
1891 ms |
| メモリ |
92396 KiB |
コンパイルエラー
Main.cpp: In function ‘State first_state(int)’:
Main.cpp:84:23: warning: unused parameter ‘N’ [-Wunused-parameter]
84 | State first_state(int N) {
| ~~~~^
Main.cpp: In function ‘Answer reconstruct_final(int, int, int, std::vector<int>&, std::vector<std::vector<State> >&)’:
Main.cpp:135:62: warning: unused parameter ‘T’ [-Wunused-parameter]
135 | Answer reconstruct_final(int N, int cx, int cy, vector<int>& T, vector<vector<State>>& beam) {
| ~~~~~~~~~~~~~^
Main.cpp: In function ‘std::vector<int> reconstruct_bins(int, int, int, std::vector<int>&, std::vector<std::vector<State> >&)’:
Main.cpp:151:34: warning: unused parameter ‘N’ [-Wunused-parameter]
151 | vector<int> reconstruct_bins(int N, int cx, int cy, vector<int>& T, vector<vector<State>>& beam) {
| ~~~~^
Main.cpp: In function ‘Operation get_op(int, std::vector<int>, std::vector<int>&, std::vector<int>&, int, int, double)’:
Main.cpp:174:29: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
174 | if (idx % N < actual.size()) wage = (idx < N ? (actual[idx] + 1) / 2 : (actual[idx - N] + 0) / 2);
| ~~~~~~~~^~~~~~~~~~~~~~~
Main.cpp: In function ‘std::vector<Operation> enumerate_operation_three(int, int, int, int, std::vector<int>&, std::vector<int>&, std::vector<int>&, double, std::vector<std::vector<State> >&, std::vector<std::vector<std::vector<Operation> > >&)’:
Main.cpp:251:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<Operation>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
251 | for (int i = 0; i < answer.size(); i++) answer[i] = Operation{ vector<int>{}, 100000, 0 };
| ~~^~~~~~~~~~~~~~~
Main.cpp:268:35: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
268 | for (int i = 0; i < unused_list.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:269:47: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
269 | for (int j = i + 1; j < unused_list.size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:270:55: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
270 | for (int k = j + 1; k < unused_list.size(); k++) {
| ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:245:72: warning: unused parameter ‘select’ [-Wunused-parameter]
245 | vector<Operation> enumerate_operation_three(int N, int cx, int cy, int select, vector<int>& T, vector<int>& cost, vector<int>& actual, double remain_mul, vector<vector<State>>& beam, vector<vector<vector<Operation>>>& cand) {
| ~~~~^~~~~~
Main.cpp:245:219: warning: unused parameter ‘cand’ [-Wunused-parameter]
245 | vector<Operation> enumerate_operation_three(int N, int cx, int cy, int select, vector<int>& T, vector<int>& cost, vector<int>& actual, double remain_mul, vector<vector<State>>& beam, vector<vector<vector<Operation>>>& cand) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
Main.cpp: In function ‘std::vector<Operation> enumerate_operation_four(int, int, int, int, std::vector<int>&, std::vector<int>&, std::vector<int>&, double, std::vector<std::vector<State> >&, std::vector<std::vector<std::vector<Operation> > >&)’:
Main.cpp:332:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<Operation>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
332 | for (int i = 0; i < answer.size(); i++) answer[i] = Operation{ vector<int>{}, 100000, 0 };
| ~~^~~~~~~~~~~~~~~
Main.cpp:349:35: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
349 | for (int i = 0; i < unused_list.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:350:47: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
350 | for (int j = i + 1; j < unused_list.size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:351:55: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
351 | for (int k = j + 1; k < unused_list.size(); k++) {
| ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:352:63: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
352 | for (int l = k + 1; l < unused_list.size(); l++) {
| ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:326:71: warning: unused parameter ‘select’ [-Wunused-parameter]
326 | vector<Operation> enumerate_operation_four(int N, int cx, int cy, int select, vector<int>& T, vector<int>& cost, vector<int>& actual, double remain_mul, vector<vector<State>>& beam, vector<vector<vector<Operation>>>& cand) {
| ~~~~^~~~~~
Main.cpp:326:218: warning: unused parameter ‘cand’ [-Wunused-parameter]
326 | vector<Operation> enumerate_operation_four(int N, int cx, int cy, int select, vector<int>& T, vector<int>& cost, vector<int>& actual, double remain_mul, vector<vector<State>>& beam, vector<vector<vector<Operation>>>& cand) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
Main.cpp: In function ‘std::pair<int, Answer> solver_main(int, int, std::vector<int>, std::vector<int>&, std::vector<std::vector<std::vector<Operation> > >&, int, double)’:
Main.cpp:479:35: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<State>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
479 | for (int i = 0; i < beam[steps].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:523:52: warning: comparison of integer expressions of different signedness: ‘std::vector<State>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
523 | if (beam[steps + 1].size() == WIDTH) break;
| ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
Main.cpp:531:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<State>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
531 | if (i >= beam[N].size()) continue;
| ~~^~~~~~~~~~~~~~~~~
ジャッジ結果
| セット名 |
test_ALL |
| 得点 / 配点 |
149929536 / 150000000 |
| 結果 |
|
| セット名 |
テストケース |
| test_ALL |
test_0000.txt, test_0001.txt, test_0002.txt, test_0003.txt, test_0004.txt, test_0005.txt, test_0006.txt, test_0007.txt, test_0008.txt, test_0009.txt, test_0010.txt, test_0011.txt, test_0012.txt, test_0013.txt, test_0014.txt, test_0015.txt, test_0016.txt, test_0017.txt, test_0018.txt, test_0019.txt, test_0020.txt, test_0021.txt, test_0022.txt, test_0023.txt, test_0024.txt, test_0025.txt, test_0026.txt, test_0027.txt, test_0028.txt, test_0029.txt, test_0030.txt, test_0031.txt, test_0032.txt, test_0033.txt, test_0034.txt, test_0035.txt, test_0036.txt, test_0037.txt, test_0038.txt, test_0039.txt, test_0040.txt, test_0041.txt, test_0042.txt, test_0043.txt, test_0044.txt, test_0045.txt, test_0046.txt, test_0047.txt, test_0048.txt, test_0049.txt, test_0050.txt, test_0051.txt, test_0052.txt, test_0053.txt, test_0054.txt, test_0055.txt, test_0056.txt, test_0057.txt, test_0058.txt, test_0059.txt, test_0060.txt, test_0061.txt, test_0062.txt, test_0063.txt, test_0064.txt, test_0065.txt, test_0066.txt, test_0067.txt, test_0068.txt, test_0069.txt, test_0070.txt, test_0071.txt, test_0072.txt, test_0073.txt, test_0074.txt, test_0075.txt, test_0076.txt, test_0077.txt, test_0078.txt, test_0079.txt, test_0080.txt, test_0081.txt, test_0082.txt, test_0083.txt, test_0084.txt, test_0085.txt, test_0086.txt, test_0087.txt, test_0088.txt, test_0089.txt, test_0090.txt, test_0091.txt, test_0092.txt, test_0093.txt, test_0094.txt, test_0095.txt, test_0096.txt, test_0097.txt, test_0098.txt, test_0099.txt, test_0100.txt, test_0101.txt, test_0102.txt, test_0103.txt, test_0104.txt, test_0105.txt, test_0106.txt, test_0107.txt, test_0108.txt, test_0109.txt, test_0110.txt, test_0111.txt, test_0112.txt, test_0113.txt, test_0114.txt, test_0115.txt, test_0116.txt, test_0117.txt, test_0118.txt, test_0119.txt, test_0120.txt, test_0121.txt, test_0122.txt, test_0123.txt, test_0124.txt, test_0125.txt, test_0126.txt, test_0127.txt, test_0128.txt, test_0129.txt, test_0130.txt, test_0131.txt, test_0132.txt, test_0133.txt, test_0134.txt, test_0135.txt, test_0136.txt, test_0137.txt, test_0138.txt, test_0139.txt, test_0140.txt, test_0141.txt, test_0142.txt, test_0143.txt, test_0144.txt, test_0145.txt, test_0146.txt, test_0147.txt, test_0148.txt, test_0149.txt |
| ケース名 |
結果 |
実行時間 |
メモリ |
| test_0000.txt |
AC |
1824 ms |
92396 KiB |
| test_0001.txt |
AC |
1848 ms |
91508 KiB |
| test_0002.txt |
AC |
1261 ms |
91700 KiB |
| test_0003.txt |
AC |
1678 ms |
91432 KiB |
| test_0004.txt |
AC |
1832 ms |
91512 KiB |
| test_0005.txt |
AC |
1847 ms |
91336 KiB |
| test_0006.txt |
AC |
1833 ms |
91356 KiB |
| test_0007.txt |
AC |
1827 ms |
91264 KiB |
| test_0008.txt |
AC |
1789 ms |
91192 KiB |
| test_0009.txt |
AC |
1854 ms |
91512 KiB |
| test_0010.txt |
AC |
1846 ms |
90764 KiB |
| test_0011.txt |
AC |
1833 ms |
91392 KiB |
| test_0012.txt |
AC |
1786 ms |
91400 KiB |
| test_0013.txt |
AC |
1805 ms |
91276 KiB |
| test_0014.txt |
AC |
1755 ms |
91448 KiB |
| test_0015.txt |
AC |
1827 ms |
91808 KiB |
| test_0016.txt |
AC |
1794 ms |
91032 KiB |
| test_0017.txt |
AC |
1778 ms |
91248 KiB |
| test_0018.txt |
AC |
1838 ms |
91156 KiB |
| test_0019.txt |
AC |
1832 ms |
91416 KiB |
| test_0020.txt |
AC |
1826 ms |
91296 KiB |
| test_0021.txt |
AC |
1839 ms |
91280 KiB |
| test_0022.txt |
AC |
1838 ms |
91372 KiB |
| test_0023.txt |
AC |
1783 ms |
91808 KiB |
| test_0024.txt |
AC |
1706 ms |
91300 KiB |
| test_0025.txt |
AC |
1802 ms |
91528 KiB |
| test_0026.txt |
AC |
1862 ms |
91040 KiB |
| test_0027.txt |
AC |
1834 ms |
91332 KiB |
| test_0028.txt |
AC |
1830 ms |
91020 KiB |
| test_0029.txt |
AC |
1789 ms |
91356 KiB |
| test_0030.txt |
AC |
1853 ms |
91540 KiB |
| test_0031.txt |
AC |
1833 ms |
91784 KiB |
| test_0032.txt |
AC |
1840 ms |
91796 KiB |
| test_0033.txt |
AC |
1782 ms |
91264 KiB |
| test_0034.txt |
AC |
1828 ms |
91532 KiB |
| test_0035.txt |
AC |
1817 ms |
91340 KiB |
| test_0036.txt |
AC |
1834 ms |
91284 KiB |
| test_0037.txt |
AC |
1803 ms |
91328 KiB |
| test_0038.txt |
AC |
1848 ms |
91256 KiB |
| test_0039.txt |
AC |
1844 ms |
91008 KiB |
| test_0040.txt |
AC |
1837 ms |
91016 KiB |
| test_0041.txt |
AC |
1759 ms |
91588 KiB |
| test_0042.txt |
AC |
1830 ms |
91400 KiB |
| test_0043.txt |
AC |
1800 ms |
91556 KiB |
| test_0044.txt |
AC |
1808 ms |
91572 KiB |
| test_0045.txt |
AC |
1845 ms |
91184 KiB |
| test_0046.txt |
AC |
1827 ms |
91048 KiB |
| test_0047.txt |
AC |
1846 ms |
91224 KiB |
| test_0048.txt |
AC |
1847 ms |
91428 KiB |
| test_0049.txt |
AC |
1853 ms |
90760 KiB |
| test_0050.txt |
AC |
1809 ms |
91544 KiB |
| test_0051.txt |
AC |
1745 ms |
91632 KiB |
| test_0052.txt |
AC |
1838 ms |
91120 KiB |
| test_0053.txt |
AC |
1867 ms |
91432 KiB |
| test_0054.txt |
AC |
1831 ms |
91284 KiB |
| test_0055.txt |
AC |
1838 ms |
91556 KiB |
| test_0056.txt |
AC |
1798 ms |
91364 KiB |
| test_0057.txt |
AC |
1878 ms |
91380 KiB |
| test_0058.txt |
AC |
1818 ms |
91360 KiB |
| test_0059.txt |
AC |
1843 ms |
91544 KiB |
| test_0060.txt |
AC |
1817 ms |
91392 KiB |
| test_0061.txt |
AC |
1813 ms |
91392 KiB |
| test_0062.txt |
AC |
1808 ms |
91296 KiB |
| test_0063.txt |
AC |
1819 ms |
91776 KiB |
| test_0064.txt |
AC |
1764 ms |
91460 KiB |
| test_0065.txt |
AC |
1818 ms |
91588 KiB |
| test_0066.txt |
AC |
1822 ms |
91420 KiB |
| test_0067.txt |
AC |
1846 ms |
91328 KiB |
| test_0068.txt |
AC |
1829 ms |
91556 KiB |
| test_0069.txt |
AC |
1843 ms |
91640 KiB |
| test_0070.txt |
AC |
1847 ms |
91580 KiB |
| test_0071.txt |
AC |
1844 ms |
92072 KiB |
| test_0072.txt |
AC |
1816 ms |
91312 KiB |
| test_0073.txt |
AC |
1830 ms |
91524 KiB |
| test_0074.txt |
AC |
1847 ms |
91356 KiB |
| test_0075.txt |
AC |
1848 ms |
91584 KiB |
| test_0076.txt |
AC |
1768 ms |
91620 KiB |
| test_0077.txt |
AC |
1891 ms |
91044 KiB |
| test_0078.txt |
AC |
1857 ms |
91268 KiB |
| test_0079.txt |
AC |
1759 ms |
91560 KiB |
| test_0080.txt |
AC |
1832 ms |
91556 KiB |
| test_0081.txt |
AC |
1825 ms |
91188 KiB |
| test_0082.txt |
AC |
1848 ms |
91576 KiB |
| test_0083.txt |
AC |
1824 ms |
91316 KiB |
| test_0084.txt |
AC |
1818 ms |
91296 KiB |
| test_0085.txt |
AC |
1695 ms |
91352 KiB |
| test_0086.txt |
AC |
1851 ms |
91268 KiB |
| test_0087.txt |
AC |
1741 ms |
91408 KiB |
| test_0088.txt |
AC |
1823 ms |
91244 KiB |
| test_0089.txt |
AC |
1849 ms |
91512 KiB |
| test_0090.txt |
AC |
1781 ms |
92192 KiB |
| test_0091.txt |
AC |
1828 ms |
91396 KiB |
| test_0092.txt |
AC |
1841 ms |
91464 KiB |
| test_0093.txt |
AC |
1808 ms |
91776 KiB |
| test_0094.txt |
AC |
1829 ms |
91280 KiB |
| test_0095.txt |
AC |
1844 ms |
91560 KiB |
| test_0096.txt |
AC |
1828 ms |
91604 KiB |
| test_0097.txt |
AC |
1816 ms |
91460 KiB |
| test_0098.txt |
AC |
1840 ms |
91288 KiB |
| test_0099.txt |
AC |
1785 ms |
91196 KiB |
| test_0100.txt |
AC |
1837 ms |
91760 KiB |
| test_0101.txt |
AC |
1759 ms |
91540 KiB |
| test_0102.txt |
AC |
1856 ms |
91840 KiB |
| test_0103.txt |
AC |
1821 ms |
91704 KiB |
| test_0104.txt |
AC |
1848 ms |
91544 KiB |
| test_0105.txt |
AC |
1847 ms |
91200 KiB |
| test_0106.txt |
AC |
1841 ms |
91284 KiB |
| test_0107.txt |
AC |
1810 ms |
91488 KiB |
| test_0108.txt |
AC |
1773 ms |
91344 KiB |
| test_0109.txt |
AC |
1847 ms |
91744 KiB |
| test_0110.txt |
AC |
1835 ms |
91556 KiB |
| test_0111.txt |
AC |
1780 ms |
92388 KiB |
| test_0112.txt |
AC |
1837 ms |
91296 KiB |
| test_0113.txt |
AC |
1848 ms |
91552 KiB |
| test_0114.txt |
AC |
1823 ms |
91484 KiB |
| test_0115.txt |
AC |
1773 ms |
91580 KiB |
| test_0116.txt |
AC |
1847 ms |
91300 KiB |
| test_0117.txt |
AC |
1854 ms |
91432 KiB |
| test_0118.txt |
AC |
1791 ms |
91296 KiB |
| test_0119.txt |
AC |
1770 ms |
91244 KiB |
| test_0120.txt |
AC |
1763 ms |
91272 KiB |
| test_0121.txt |
AC |
1836 ms |
91452 KiB |
| test_0122.txt |
AC |
1846 ms |
92036 KiB |
| test_0123.txt |
AC |
1844 ms |
92356 KiB |
| test_0124.txt |
AC |
1830 ms |
91012 KiB |
| test_0125.txt |
AC |
1831 ms |
91260 KiB |
| test_0126.txt |
AC |
1840 ms |
91532 KiB |
| test_0127.txt |
AC |
1839 ms |
91500 KiB |
| test_0128.txt |
AC |
1822 ms |
91568 KiB |
| test_0129.txt |
AC |
1822 ms |
91540 KiB |
| test_0130.txt |
AC |
1796 ms |
91520 KiB |
| test_0131.txt |
AC |
1838 ms |
91408 KiB |
| test_0132.txt |
AC |
1858 ms |
91464 KiB |
| test_0133.txt |
AC |
1842 ms |
91688 KiB |
| test_0134.txt |
AC |
1763 ms |
91456 KiB |
| test_0135.txt |
AC |
1799 ms |
91616 KiB |
| test_0136.txt |
AC |
1841 ms |
91684 KiB |
| test_0137.txt |
AC |
1835 ms |
90716 KiB |
| test_0138.txt |
AC |
1789 ms |
91596 KiB |
| test_0139.txt |
AC |
1791 ms |
91092 KiB |
| test_0140.txt |
AC |
1845 ms |
91624 KiB |
| test_0141.txt |
AC |
1792 ms |
91244 KiB |
| test_0142.txt |
AC |
1847 ms |
91116 KiB |
| test_0143.txt |
AC |
1816 ms |
91468 KiB |
| test_0144.txt |
AC |
1792 ms |
91796 KiB |
| test_0145.txt |
AC |
1833 ms |
91244 KiB |
| test_0146.txt |
AC |
1839 ms |
91280 KiB |
| test_0147.txt |
AC |
1825 ms |
91268 KiB |
| test_0148.txt |
AC |
1808 ms |
91280 KiB |
| test_0149.txt |
AC |
1842 ms |
90908 KiB |