結果
| 問題 |
No.1152 10億ゲーム
|
| コンテスト | |
| ユーザー |
 simasima_71
|
| 提出日時 | 2020-08-07 22:20:51 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,610 bytes |
| コンパイル時間 | 1,596 ms |
| コンパイル使用メモリ | 118,420 KB |
| 実行使用メモリ | 52,004 KB |
| 平均クエリ数 | 5.90 |
| 最終ジャッジ日時 | 2024-07-17 04:50:10 |
| 合計ジャッジ時間 | 6,599 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 7 WA * 5 TLE * 1 -- * 37 |
ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <fstream>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
#include <cassert>
#pragma warning (disable: 4996)
using namespace std;
using ll = long long;
unsigned euclidean_gcd(unsigned a, unsigned b) {
if (a < b) return euclidean_gcd(b, a);
unsigned r;
while ((r = a % b)) {
a = b;
b = r;
}
return b;
}
ll ll_gcd(ll a, ll b) {
if (a < b) return ll_gcd(b, a);
ll r;
while ((r = a % b)) {
a = b;
b = r;
}
return b;
}
struct UnionFind {
vector <ll> par;
vector <ll> siz;
UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
for (ll i = 0; i < sz_; ++i) par[i] = i;
}
void init(ll sz_) {
par.resize(sz_);
siz.assign(sz_, 1LL);
for (ll i = 0; i < sz_; ++i) par[i] = i;
}
ll root(ll x) {
while (par[x] != x) {
x = par[x] = par[par[x]];
}
return x;
}
bool merge(ll x, ll y) {
x = root(x);
y = root(y);
if (x == y) return false;
if (siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
par[y] = x;
return true;
}
bool issame(ll x, ll y) {
return root(x) == root(y);
}
ll size(ll x) {
return siz[root(x)];
}
};
long long modpow(long long a, long long n, long long mod) {
if (n < 0)return 0;
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
long long modinv(long long a, long long mod) {
return modpow(a, mod - 2, mod);
}
vector<int> tpsort(vector<vector<int>>& G) {
int V = G.size();
vector<int> sorted_vertices;
queue<int> que;
vector<int> indegree(V);
for (int i = 0; i < V; i++) {
for (int j = 0; j < G[i].size(); j++) {
indegree[G[i][j]]++;
}
}
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
que.push(i);
}
}
while (que.empty() == false) {
int v = que.front();
que.pop();
for (int i = 0; i < G[v].size(); i++) {
int u = G[v][i];
indegree[u] -= 1;
if (indegree[u] == 0) que.push(u);
}
sorted_vertices.push_back(v);
}
return sorted_vertices;
}
struct Point
{
double x;
double y;
};
struct LineSegment
{
Point start;
Point end;
};
double tenkyori(const LineSegment& line, const Point& point)
{
double x0 = point.x, y0 = point.y;
double x1 = line.start.x, y1 = line.start.y;
double x2 = line.end.x, y2 = line.end.y;
double a = x2 - x1;
double b = y2 - y1;
double a2 = a * a;
double b2 = b * b;
double r2 = a2 + b2;
double tt = -(a * (x1 - x0) + b * (y1 - y0));
if (tt < 0)
return sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0));
else if (tt > r2)
return sqrt((x2 - x0) * (x2 - x0) + (y2 - y0) * (y2 - y0));
double f1 = a * (y1 - y0) - b * (x1 - x0);
return sqrt((f1 * f1) / r2);
}
void dfs1(vector<vector<ll>>& z, ll k, ll oya, ll& ans, vector<ll>& b) {
for (auto m : z[k]) {
if (m != oya)dfs1(z, m, k, ans, b);
}
vector<ll> s;
for (auto m : z[k]) {
if (m != oya)s.push_back(b[m]);
}
ll m = b.size() - 1;
for (auto d : s) {
m -= d;
}
b[k] = b.size() - m;
if (m != 0)s.push_back(m);
ll a = modinv(2, 1000000007);
for (auto d : s) {
a += 1000000007 - modinv(modpow(2, b.size() - d, 1000000007), 1000000007);
}
a += modinv(modpow(2, b.size(), 1000000007), 1000000007) * (z[k].size() - 1);
ans += a;
ans %= 1000000007;
return;
}
ll merge_cnt(vector<int>& a) {
int n = a.size();
if (n <= 1) { return 0; }
ll cnt = 0;
vector<int> b(a.begin(), a.begin() + n / 2);
vector<int> c(a.begin() + n / 2, a.end());
cnt += merge_cnt(b);
cnt += merge_cnt(c);
int ai = 0, bi = 0, ci = 0;
while (ai < n) {
if (bi < b.size() && (ci == c.size() || b[bi] <= c[ci])) {
a[ai++] = b[bi++];
}
else {
cnt += n / 2 - bi;
a[ai++] = c[ci++];
}
}
return cnt;
}
int main(void) {
ll a, b;
cin >> a >> b;
ll as = a;
ll aa = 0;
ll aaaaa = 0;
while (a % 2 == 0) {
a /= 2;
aa++;
}
while (a % 5 == 0) {
a /= 5;
aaaaa++;
}
ll fl = 0;
if (true) {
while (aa != 0) {
as /= 2;
aa--;
cout << as << endl;
if (as == b)return 0;
cin >> b;
if (as == b)return 0;
}
while (aaaaa != 9) {
as *= 5;
aaaaa++;
cout << as << endl;
if (as == b)return 0;
cin >> b;
if (as == b)return 0;
}
}
else {
while (aa != 9) {
as *= 2;
aa++;
cout << as << endl;
if (as == b)return 0;
cin >> b;
if (as == b)return 0;
}
while (aaaaa != 0) {
as /= 5;
aaaaa--;
cout << as << endl;
if (as == b)return 0;
cin >> b;
if (as == b)return 0;
}
}
ll bs = b;
ll bb = 0;
ll bbbbb = 0;
while (b % 2 == 0) {
b /= 2;
bb++;
}
while (b % 5 == 0) {
b /= 5;
bbbbb++;
}
while (true) {
if (abs(aa - bb) >= abs(aaaaa - bbbbb)) {
if (aa < bb) {
aa++;
as *= 2;
}
else {
aa--;
as /= 2;
}
}
else {
if (aaaaa < bbbbb) {
aaaaa++;
as *= 5;
}
else {
aaaaa--;
as /= 5;
}
}
cout << as << endl;
if (as == bs)return 0;
ll u;
cin >> u;
if (as == u)return 0;
if (bs * 2 == u)bb++;
if (bs == u * 2)bb--;
if (bs * 5 == u)bbbbb++;
if (bs == u * 5)bbbbb--;
bs = u;
}
}