QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #723776 | #7695. Double Up | MattTheNub# | WA | 1ms | 4024kb | C++23 | 7.0kb | 2024-11-08 00:19:37 | 2024-11-08 00:19:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using v = vector<T>;
using ll = long long;
using dd = long double;
using int2 = pair<int, int>;
using ll2 = pair<ll, ll>;
using dd2 = pair<dd, dd>;
#define f first
#define s second
#define all(x) begin(x), end(x)
istream &__cin = cin;
#ifdef DEV_MODE
#include "debug.h"
__cinwrapper __cin_wrapper;
#define cin __cin_wrapper
#else
#define dbg(...)
#define dbg2d(...)
#endif
template <class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
in >> p.first >> p.second;
return in;
}
template <class T> istream &operator>>(istream &in, v<T> &v) {
for (auto &x : v)
in >> x;
return in;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
/*
_______________________________________
( If you don't fail at least 90% of the )
( time, you're not aiming high enough. )
( )
( - Alan Kay )
---------------------------------------
o ^__^
o (oo)\_______
(__)\ )\/\
||----w |
|| ||
*/
const bool INTERACTIVE = false;
const bool MULTITEST = false;
/******************************************************************************/
#pragma region templates
using i128 = __int128;
ostream &operator<<(ostream &out, i128 x) {
if (x == 0)
return out << "0";
string y = "";
bool neg = x < 0;
if (neg)
x = -x;
while (x) {
y.push_back((char)(x % 10) + '0');
x /= 10;
}
if (neg) {
y.push_back('-');
}
reverse(all(y));
return out << y;
}
#pragma endregion templates
const string vals[] = {"1",
"2",
"4",
"8",
"16",
"32",
"64",
"128",
"256",
"512",
"1024",
"2048",
"4096",
"8192",
"16384",
"32768",
"65536",
"131072",
"262144",
"524288",
"1048576",
"2097152",
"4194304",
"8388608",
"16777216",
"33554432",
"67108864",
"134217728",
"268435456",
"536870912",
"1073741824",
"2147483648",
"4294967296",
"8589934592",
"17179869184",
"34359738368",
"68719476736",
"137438953472",
"274877906944",
"549755813888",
"1099511627776",
"2199023255552",
"4398046511104",
"8796093022208",
"17592186044416",
"35184372088832",
"70368744177664",
"140737488355328",
"281474976710656",
"562949953421312",
"1125899906842624",
"2251799813685248",
"4503599627370496",
"9007199254740992",
"18014398509481984",
"36028797018963968",
"72057594037927936",
"144115188075855872",
"288230376151711744",
"576460752303423488",
"1152921504606846976",
"2305843009213693952",
"4611686018427387904",
"9223372036854775808",
"18446744073709551616",
"36893488147419103232",
"73786976294838206464",
"147573952589676412928",
"295147905179352825856",
"590295810358705651712",
"1180591620717411303424",
"2361183241434822606848",
"4722366482869645213696",
"9444732965739290427392",
"18889465931478580854784",
"37778931862957161709568",
"75557863725914323419136",
"151115727451828646838272",
"302231454903657293676544",
"604462909807314587353088",
"1208925819614629174706176",
"2417851639229258349412352",
"4835703278458516698824704",
"9671406556917033397649408",
"19342813113834066795298816",
"38685626227668133590597632",
"77371252455336267181195264",
"154742504910672534362390528",
"309485009821345068724781056",
"618970019642690137449562112",
"1237940039285380274899124224",
"2475880078570760549798248448",
"4951760157141521099596496896",
"9903520314283042199192993792",
"19807040628566084398385987584",
"39614081257132168796771975168",
"79228162514264337593543950336",
"158456325028528675187087900672",
"316912650057057350374175801344",
"633825300114114700748351602688",
"1267650600228229401496703205376"};
void solve() {
int n;
cin >> n;
v<int> a(n);
for (int i = 0; i < n; i++) {
string s;
cin >> s;
while (vals[a[i]] != s)
a[i]++;
}
v<v<int>> dp(n, v<int>(112, 1e9));
for (int i = 0; i < n; i++) {
dp[i][a[i]] = i;
}
i128 ans = 1;
for (int j = 0; j < 111; j++) {
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1)
dp[i][j] = min(dp[i][j], dp[i + 1][j]);
if (dp[i][j] < n - 1)
dp[i][j + 1] = min(dp[i][j + 1], dp[dp[i][j] + 1][j]);
}
if (dp[0][j + 1] < n)
ans = (i128)1 << (j + 1);
}
cout << ans;
}
int main() {
#ifdef DEV_MODE
debug_start(INTERACTIVE, "d.txt");
#else
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int t;
if (MULTITEST)
cin >> t;
else
t = 1;
while (t--)
solve();
#ifdef DEV_MODE
debug_exit(INTERACTIVE);
#endif
}
#ifdef DEV_MODE
#include "debug.cpp"
#endif
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3568kb
input:
5 4 2 2 1 8
output:
16
result:
ok single line: '16'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
512
result:
ok single line: '512'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
1000 1267650600228229401496703205376 1267650600228229401496703205376 1267650600228229401496703205376 1267650600228229401496703205376 1267650600228229401496703205376 1267650600228229401496703205376 1267650600228229401496703205376 1267650600228229401496703205376 1267650600228229401496703205376 1267650...
output:
649037107316853453566312041152512
result:
ok single line: '649037107316853453566312041152512'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
1 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
1 2
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
1 4294967296
output:
4294967296
result:
ok single line: '4294967296'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
1 18446744073709551616
output:
18446744073709551616
result:
ok single line: '18446744073709551616'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
1 1267650600228229401496703205376
output:
1267650600228229401496703205376
result:
ok single line: '1267650600228229401496703205376'
Test #9:
score: -100
Wrong Answer
time: 1ms
memory: 3812kb
input:
384 18014398509481984 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 10737418...
output:
576460752303423488
result:
wrong answer 1st lines differ - expected: '618970019642690137449562112', found: '576460752303423488'