QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363527 | #7695. Double Up | pipoika# | AC ✓ | 1068ms | 11764kb | C++20 | 4.5kb | 2024-03-23 23:50:58 | 2024-03-23 23:50:58 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,j,k) for (int i=j;i<(k);++i)
#define all(i) (i).begin(),(i).end()
#define sz(i) (int)(i).size()
using namespace std;
typedef vector<int> vi;
const map<string,int> powmap = {{"1",0},
{"2",1},
{"4",2},
{"8",3},
{"16",4},
{"32",5},
{"64",6},
{"128",7},
{"256",8},
{"512",9},
{"1024",10},
{"2048",11},
{"4096",12},
{"8192",13},
{"16384",14},
{"32768",15},
{"65536",16},
{"131072",17},
{"262144",18},
{"524288",19},
{"1048576",20},
{"2097152",21},
{"4194304",22},
{"8388608",23},
{"16777216",24},
{"33554432",25},
{"67108864",26},
{"134217728",27},
{"268435456",28},
{"536870912",29},
{"1073741824",30},
{"2147483648",31},
{"4294967296",32},
{"8589934592",33},
{"17179869184",34},
{"34359738368",35},
{"68719476736",36},
{"137438953472",37},
{"274877906944",38},
{"549755813888",39},
{"1099511627776",40},
{"2199023255552",41},
{"4398046511104",42},
{"8796093022208",43},
{"17592186044416",44},
{"35184372088832",45},
{"70368744177664",46},
{"140737488355328",47},
{"281474976710656",48},
{"562949953421312",49},
{"1125899906842624",50},
{"2251799813685248",51},
{"4503599627370496",52},
{"9007199254740992",53},
{"18014398509481984",54},
{"36028797018963968",55},
{"72057594037927936",56},
{"144115188075855872",57},
{"288230376151711744",58},
{"576460752303423488",59},
{"1152921504606846976",60},
{"2305843009213693952",61},
{"4611686018427387904",62},
{"9223372036854775808",63},
{"18446744073709551616",64},
{"36893488147419103232",65},
{"73786976294838206464",66},
{"147573952589676412928",67},
{"295147905179352825856",68},
{"590295810358705651712",69},
{"1180591620717411303424",70},
{"2361183241434822606848",71},
{"4722366482869645213696",72},
{"9444732965739290427392",73},
{"18889465931478580854784",74},
{"37778931862957161709568",75},
{"75557863725914323419136",76},
{"151115727451828646838272",77},
{"302231454903657293676544",78},
{"604462909807314587353088",79},
{"1208925819614629174706176",80},
{"2417851639229258349412352",81},
{"4835703278458516698824704",82},
{"9671406556917033397649408",83},
{"19342813113834066795298816",84},
{"38685626227668133590597632",85},
{"77371252455336267181195264",86},
{"154742504910672534362390528",87},
{"309485009821345068724781056",88},
{"618970019642690137449562112",89},
{"1237940039285380274899124224",90},
{"2475880078570760549798248448",91},
{"4951760157141521099596496896",92},
{"9903520314283042199192993792",93},
{"19807040628566084398385987584",94},
{"39614081257132168796771975168",95},
{"79228162514264337593543950336",96},
{"158456325028528675187087900672",97},
{"316912650057057350374175801344",98},
{"633825300114114700748351602688",99},
{"1267650600228229401496703205376",100},
{"2535301200456458802993406410752",101},
{"5070602400912917605986812821504",102},
{"10141204801825835211973625643008",103},
{"20282409603651670423947251286016",104},
{"40564819207303340847894502572032",105},
{"81129638414606681695789005144064",106},
{"162259276829213363391578010288128",107},
{"324518553658426726783156020576256",108},
{"649037107316853453566312041152512",109},
{"1298074214633706907132624082305024",110},
{"2596148429267413814265248164610048",111},
{"5192296858534827628530496329220096",112},
{"10384593717069655257060992658440192",113},
{"20769187434139310514121985316880384",114},
{"41538374868278621028243970633760768",115},
{"83076749736557242056487941267521536",116},
{"166153499473114484112975882535043072",117},
{"332306998946228968225951765070086144",118},
{"664613997892457936451903530140172288",119},};
int rpow() {
string w;cin>>w;
assert(powmap.count(w));
return powmap.at(w);
}
vi nums;
const int SIZE = 2000000;
int memo[SIZE];
int solve(int low, int high) {
if (low == high) return nums[low];
int key = (low << 10) | high;
if (memo[key]) return memo[key];
int ans = solve(low+1, high);
ans = max(ans, solve(low, high-1));
rep(split, low, high) {
int left = solve(low, split);
int right = solve(split+1, high);
int sub = max(left, right);
if (left == right) ++sub;
ans = max(ans, sub);
}
return memo[key] = ans;
}
int main() {
int n;
cin >> n;
rep(i,0,SIZE) memo[i]=0;
nums.resize(n);
rep(i,0,n) nums[i] = rpow();
int ans = solve(0,n-1);
string output;
for (auto [k, v] : powmap) if (v == ans) {
// cout << k << ' ' << v << endl;
// output =
cout << k << endl;
break;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11504kb
input:
5 4 2 2 1 8
output:
16
result:
ok single line: '16'
Test #2:
score: 0
Accepted
time: 1068ms
memory: 11736kb
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: 1058ms
memory: 11740kb
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: 11696kb
input:
1 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 2ms
memory: 11472kb
input:
1 2
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 11404kb
input:
1 4294967296
output:
4294967296
result:
ok single line: '4294967296'
Test #7:
score: 0
Accepted
time: 2ms
memory: 11460kb
input:
1 18446744073709551616
output:
18446744073709551616
result:
ok single line: '18446744073709551616'
Test #8:
score: 0
Accepted
time: 2ms
memory: 11400kb
input:
1 1267650600228229401496703205376
output:
1267650600228229401496703205376
result:
ok single line: '1267650600228229401496703205376'
Test #9:
score: 0
Accepted
time: 46ms
memory: 11484kb
input:
384 18014398509481984 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 72057594037927936 10737418...
output:
618970019642690137449562112
result:
ok single line: '618970019642690137449562112'
Test #10:
score: 0
Accepted
time: 69ms
memory: 11724kb
input:
430 36893488147419103232 128 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248 2251799813685248...
output:
158456325028528675187087900672
result:
ok single line: '158456325028528675187087900672'
Test #11:
score: 0
Accepted
time: 123ms
memory: 11500kb
input:
527 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 1099511627776 10...
output:
158456325028528675187087900672
result:
ok single line: '158456325028528675187087900672'
Test #12:
score: 0
Accepted
time: 523ms
memory: 11752kb
input:
809 1073741824 77371252455336267181195264 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 2097152 20...
output:
19807040628566084398385987584
result:
ok single line: '19807040628566084398385987584'
Test #13:
score: 0
Accepted
time: 68ms
memory: 11500kb
input:
435 618970019642690137449562112 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 65536 128 128 128 128 128 128 128 128 128 128 128 128 128 ...
output:
316912650057057350374175801344
result:
ok single line: '316912650057057350374175801344'
Test #14:
score: 0
Accepted
time: 622ms
memory: 11764kb
input:
857 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 4398046511104 43...
output:
1267650600228229401496703205376
result:
ok single line: '1267650600228229401496703205376'
Test #15:
score: 0
Accepted
time: 442ms
memory: 11556kb
input:
765 17592186044416 2417851639229258349412352 2417851639229258349412352 2417851639229258349412352 2417851639229258349412352 2417851639229258349412352 2417851639229258349412352 2417851639229258349412352 2417851639229258349412352 2417851639229258349412352 2417851639229258349412352 241785163922925834941...
output:
1237940039285380274899124224
result:
ok single line: '1237940039285380274899124224'
Test #16:
score: 0
Accepted
time: 0ms
memory: 11404kb
input:
122 2097152 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 18014398509481984 ...
output:
10141204801825835211973625643008
result:
ok single line: '10141204801825835211973625643008'
Test #17:
score: 0
Accepted
time: 102ms
memory: 11496kb
input:
491 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 8192 562949953421312 9444732965739290427392 9444732965739290427392 9444732965739290427392 9444732965739290427392 9444732965739290427392 94447329657392904273...
output:
1267650600228229401496703205376
result:
ok single line: '1267650600228229401496703205376'
Test #18:
score: 0
Accepted
time: 3ms
memory: 11668kb
input:
164 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 549755813888 5497558138...
output:
20282409603651670423947251286016
result:
ok single line: '20282409603651670423947251286016'