QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#245311 | #7659. Highway Combinatorics | PetroTarnavskyi# | AC ✓ | 1144ms | 272788kb | C++20 | 2.7kb | 2023-11-09 20:33:27 | 2023-11-09 20:33:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int mod = 1e9 + 7;
int add(int a, int b)
{
return a + b < mod ? a + b : a + b - mod;
}
int mult(int a, int b)
{
return (LL)a * b % mod;
}
int binpow(int a, int n)
{
int res = 1;
while(n)
{
if(n & 1)
res = mult(res, a);
a = mult(a, a);
n /= 2;
}
return res;
}
int inv(int a)
{
return binpow(a, mod - 2);
}
const int N = 200;
int f[N];
const int CNT = 90;
const int LEN = 92;
unordered_map<int, int> hs;
VI hashes[LEN];
VI get(int val)
{
VI res;
while(true)
{
assert(hs.count(val) != 0);
int id = hs[val];
if(id == -1)
break;
res.PB(id);
val = mult(val, inv(f[id]));
}
return res;
}
void solve(int n)
{
VI lens;
for(auto [val, toL] : hs)
{
int nval = mult(n, inv(val));
if(!hs.count(nval))
continue;
VI L = get(val);
VI R = get(nval);
lens = L;
for(int i : R)
lens.PB(i);
assert(SZ(lens) != 0);
if(SZ(lens) == 0)
continue;
else
break;
}
FOR(i, 1, 197)
if(f[i] == n)
lens = {i};
if(SZ(lens) == 0)
lens = {0};
//assert(SZ(lens) != 0);
//int cur = 1;
//for(int i : lens)
// cur = mult(cur, f[i]);
//assert(cur == n);
FOR(t, 0, 2)
{
FOR(i, 0, SZ(lens))
{
FOR(j, 0, lens[i])
cout << ".";
cout << "#";
}
cout << "\n";
}
}
mt19937 rng(47);
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
f[0] = 1;
f[1] = 1;
FOR(i, 2, N)
f[i] = add(f[i - 1], f[i - 2]);
hs.reserve(1 << 23);
hs[1] = -1;
hashes[0].PB(1);
FOR(i, 1, CNT)
{
FOR(len, 0, LEN)
{
if(len + i + 1 >= LEN)
break;
for(int val : hashes[len])
{
int nval = mult(val, f[i]);
if(hs.count(nval))
continue;
hs[nval] = i;
hashes[len + i + 1].PB(nval);
}
}
}
FOR(i, CNT, 99)
hs[f[i]] = i;
//cerr << SZ(hs) << endl;
//cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
//return 0;
//FOR(it, 1, 7000)
//{
// int n = rng() % mod;
// solve(n);
//}
//cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
//return 0;
int n;
cin >> n;
if(n == 0)
{
cout << "##.\n";
cout << ".##\n";
return 0;
}
solve(n);
//assert(n != 0);
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 878ms
memory: 269092kb
input:
10
output:
...............................................................#...............#.......#..#..............................#......................#....#...#..# ...............................................................#...............#.......#..#..............................#.......................
result:
ok res = 10
Test #2:
score: 0
Accepted
time: 912ms
memory: 272308kb
input:
27
output:
......................................................................#........#.......#..#.......................#...................#.......#.......#.......#......#....#..#..# ......................................................................#........#.......#..#.......................#..........
result:
ok res = 27
Test #3:
score: 0
Accepted
time: 853ms
memory: 269144kb
input:
1000000006
output:
.................................................................................#....#...#................#..............#.............#........#......#......#..#..#..#..#..#..# .................................................................................#....#...#................#................
result:
ok res = 1000000006
Test #4:
score: 0
Accepted
time: 887ms
memory: 271172kb
input:
1000000000
output:
.................................................................................#..#..#..#................#..............#.............#........#.......#......#......#....#..#..#..# .................................................................................#..#..#..#................#............
result:
ok res = 1000000000
Test #5:
score: 0
Accepted
time: 870ms
memory: 270588kb
input:
0
output:
##. .##
result:
ok res = 0
Test #6:
score: 0
Accepted
time: 876ms
memory: 269744kb
input:
1
output:
.# .#
result:
ok res = 1
Test #7:
score: 0
Accepted
time: 878ms
memory: 272228kb
input:
7
output:
...............................................................#...............#.......#..#..............................#......................#.......# ...............................................................#...............#.......#..#..............................#......................#....
result:
ok res = 7
Test #8:
score: 0
Accepted
time: 886ms
memory: 272268kb
input:
144000001
output:
.................................................................#........................#.......................#...................#.................#.........#....#...#..# .................................................................#........................#.......................#............
result:
ok res = 144000001
Test #9:
score: 0
Accepted
time: 857ms
memory: 269188kb
input:
46750697
output:
.................................................................#........................#.....................#...................#..........#.........#........#......#...#...#...# .................................................................#........................#.....................#.......
result:
ok res = 46750697
Test #10:
score: 0
Accepted
time: 877ms
memory: 270036kb
input:
12345678
output:
...........................................................#...................#..........#................#................#.......#.......#.......#....#....#....#..#..#..#..# ...........................................................#...................#..........#................#..................
result:
ok res = 12345678
Test #11:
score: 0
Accepted
time: 914ms
memory: 272008kb
input:
102334155
output:
.......................................# .......................................#
result:
ok res = 102334155
Test #12:
score: 0
Accepted
time: 890ms
memory: 271864kb
input:
165580141
output:
........................................# ........................................#
result:
ok res = 165580141
Test #13:
score: 0
Accepted
time: 866ms
memory: 271620kb
input:
8390086
output:
.......................................................................# .......................................................................#
result:
ok res = 8390086
Test #14:
score: 0
Accepted
time: 890ms
memory: 269044kb
input:
210345902
output:
.........................................................................................# .........................................................................................#
result:
ok res = 210345902
Test #15:
score: 0
Accepted
time: 903ms
memory: 270464kb
input:
755204270
output:
..........................................................................................# ..........................................................................................#
result:
ok res = 755204270
Test #16:
score: 0
Accepted
time: 884ms
memory: 269088kb
input:
349361645
output:
.....................................................................#..................#...............................#.....................#...................#...#...#..# .....................................................................#..................#...............................#.......
result:
ok res = 349361645
Test #17:
score: 0
Accepted
time: 1144ms
memory: 271856kb
input:
529309711
output:
...........................................................#...........................#..#...........#.......#.......#....#....#....#....#...#..#..#..#..#..#..#..#..#..#..#..#..#..# ...........................................................#...........................#..#...........#.......#.........
result:
ok res = 529309711
Test #18:
score: 0
Accepted
time: 913ms
memory: 271764kb
input:
878671356
output:
..................................................................#............#....#..#..#................#.........#.......#.......#.......#....#..#..#..#..#..#..#..# ..................................................................#............#....#..#..#................#.........#.......#........
result:
ok res = 878671356
Test #19:
score: 0
Accepted
time: 861ms
memory: 269816kb
input:
141851555
output:
............................................................................................#.............................#....................#........#.......#......#...#...#..# ............................................................................................#..............................
result:
ok res = 141851555
Test #20:
score: 0
Accepted
time: 896ms
memory: 270340kb
input:
245606600
output:
................................................................#.........#...#..#..#..#..#............................#......................#.........#......#......#...#..#..# ................................................................#.........#...#..#..#..#..#............................#.....
result:
ok res = 245606600
Test #21:
score: 0
Accepted
time: 901ms
memory: 271640kb
input:
387458156
output:
........................................................................................#...................#.........#.......#......#......#......#..#..#..#..#..#..#..#..#..# ........................................................................................#...................#.........#........
result:
ok res = 387458156
Test #22:
score: 0
Accepted
time: 868ms
memory: 272472kb
input:
447800885
output:
............................................................................#.........#...#.................#..............#..........#.......#...#...# ............................................................................#.........#...#.................#..............#..........#.......#...#....
result:
ok res = 447800885
Test #23:
score: 0
Accepted
time: 853ms
memory: 271744kb
input:
981661739
output:
....................................................#............................#..#..#..#..............#..........#..........#.........#.........#......#......#...# ....................................................#............................#..#..#..#..............#..........#..........#........
result:
ok res = 981661739
Test #24:
score: 0
Accepted
time: 865ms
memory: 271908kb
input:
999999929
output:
...........................................................................#.........#....#....................#................#............#..........#..........#..........# ...........................................................................#.........#....#....................#...............
result:
ok res = 999999929
Test #25:
score: 0
Accepted
time: 875ms
memory: 270208kb
input:
35345813
output:
............................................................#..................#...#...#..#..............................#.............#.............#........#...# ............................................................#..................#...#...#..#..............................#.............#...
result:
ok res = 35345813
Test #26:
score: 0
Accepted
time: 864ms
memory: 269580kb
input:
33810803
output:
.......................................................#.................#..........#..#..#..........#........#......#......#...#...#...#...#..#..#..#..#..#..#..#..#..#..#..#..# .......................................................#.................#..........#..#..#..........#........#......#.......
result:
ok res = 33810803
Test #27:
score: 0
Accepted
time: 907ms
memory: 269316kb
input:
966289935
output:
...............................................#.......................#....#....#..#..#..#..............#.............#........#.......#....#....#....#....#..#..#..#..#..# ...............................................#.......................#....#....#..#..#..#..............#.............#..........
result:
ok res = 966289935
Test #28:
score: 0
Accepted
time: 859ms
memory: 269988kb
input:
29521716
output:
....................................................................#.........#.......#...#....................................#................................#.........#......#...# ....................................................................#.........#.......#...#.............................
result:
ok res = 29521716
Test #29:
score: 0
Accepted
time: 826ms
memory: 269040kb
input:
64472472
output:
.....................................................#........................#......#....#.........................................#.................#.......#....#....#....#..#..# .....................................................#........................#......#....#...............................
result:
ok res = 64472472
Test #30:
score: 0
Accepted
time: 887ms
memory: 271636kb
input:
158427805
output:
.............................................................................#.........#..#.............#..........#..........#.........#.........#........#..#..# .............................................................................#.........#..#.............#..........#..........#.........#...
result:
ok res = 158427805
Test #31:
score: 0
Accepted
time: 856ms
memory: 270604kb
input:
476648214
output:
........................................................#.........................#....#..#.................#............#........#......#...#...#...#...#..#..#..#..#..#..#..#..# ........................................................#.........................#....#..#.................#...............
result:
ok res = 476648214
Test #32:
score: 0
Accepted
time: 876ms
memory: 270008kb
input:
460753020
output:
......................................................................#.........#....#....#..........................#......................#................#..........#........# ......................................................................#.........#....#....#..........................#......
result:
ok res = 460753020
Test #33:
score: 0
Accepted
time: 883ms
memory: 272292kb
input:
846275927
output:
.......................................................................#.........#..#..#..#...............#......#......#......#....#....#....#....#....#....#....#....#....#....#..# .......................................................................#.........#..#..#..#...............#......#.......
result:
ok res = 846275927
Test #34:
score: 0
Accepted
time: 900ms
memory: 272268kb
input:
436044186
output:
....................................................#...............#.......#.......#..#..#.............#.............#.......#.......#.......#....#....#....#...#...#...#...#...# ....................................................#...............#.......#.......#..#..#.............#.............#.....
result:
ok res = 436044186
Test #35:
score: 0
Accepted
time: 903ms
memory: 272532kb
input:
4714726
output:
.................................................................................#...#...#...............#.............#.........#.........#........#......#...#...#...#..# .................................................................................#...#...#...............#.............#...........
result:
ok res = 4714726
Test #36:
score: 0
Accepted
time: 885ms
memory: 271116kb
input:
405106993
output:
.........................................................................#..........#.......................#...................#...............#...............#..........#..# .........................................................................#..........#.......................#..................
result:
ok res = 405106993
Test #37:
score: 0
Accepted
time: 902ms
memory: 271892kb
input:
395136214
output:
..................................................................#..............#........#.........................#........................#..................#...#..#..#..#..# ..................................................................#..............#........#.........................#........
result:
ok res = 395136214
Test #38:
score: 0
Accepted
time: 894ms
memory: 270468kb
input:
318600029
output:
.............................................................#..............#.........#..#..........................#..................#..............#......#....#...#...#...# .............................................................#..............#.........#..#..........................#..........
result:
ok res = 318600029
Test #39:
score: 0
Accepted
time: 892ms
memory: 271616kb
input:
446626687
output:
...........................................................................#.........#....#.....................................................#...............#....#...#...#...# ...........................................................................#.........#....#.................................
result:
ok res = 446626687
Test #40:
score: 0
Accepted
time: 907ms
memory: 272388kb
input:
152602867
output:
................................................................................#....#....#.............#..........#..........#.......#.......#......#......#......#......#...#...# ................................................................................#....#....#.............#..........#.......
result:
ok res = 152602867
Test #41:
score: 0
Accepted
time: 893ms
memory: 271220kb
input:
989466381
output:
..............................................................#........#......#......#....#....................#.......#.......#.......#.......#......#......#....#....#..# ..............................................................#........#......#......#....#....................#.......#.......#...
result:
ok res = 989466381
Test #42:
score: 0
Accepted
time: 875ms
memory: 270612kb
input:
936862096
output:
............................................................#...............#.......#..#..#.........................#.............#......#....#...#...#..#..#..#..#..#..#..# ............................................................#...............#.......#..#..#.........................#.............
result:
ok res = 936862096
Test #43:
score: 0
Accepted
time: 901ms
memory: 270384kb
input:
716629682
output:
.................................................#..................#..........#..........#..........#..........#.......#.......#.......#.......#......#......#......#....#....#..#..# .................................................#..................#..........#..........#..........#..........#.......
result:
ok res = 716629682
Test #44:
score: 0
Accepted
time: 895ms
memory: 271632kb
input:
777283759
output:
..........................................................#............#.......#......#...#.............................................#....#....#....#...#..#..# ..........................................................#............#.......#......#...#.............................................#...
result:
ok res = 777283759
Test #45:
score: 0
Accepted
time: 876ms
memory: 269700kb
input:
791644428
output:
.......................................................................#............#....#.........................#.....................#....#....#..# .......................................................................#............#....#.........................#.....................#....#....#...
result:
ok res = 791644428
Test #46:
score: 0
Accepted
time: 907ms
memory: 272768kb
input:
653877186
output:
............................................................................#..........#..#...........#..........#..........#..........#..........#........#.......#.......#....#...# ............................................................................#..........#..#...........#..........#.......
result:
ok res = 653877186
Test #47:
score: 0
Accepted
time: 916ms
memory: 269104kb
input:
927194288
output:
........................................................#.............................#..#...................#................#.........#.........#.........#.......#.......# ........................................................#.............................#..#...................#...................
result:
ok res = 927194288
Test #48:
score: 0
Accepted
time: 883ms
memory: 270352kb
input:
926281794
output:
.....................................................#.....................#.........#....#.....................#.................#..........#........#........#......#..#..#..#..# .....................................................#.....................#.........#....#.....................#..........
result:
ok res = 926281794
Test #49:
score: 0
Accepted
time: 906ms
memory: 269696kb
input:
244063801
output:
.............................................................#....................#...#...#..........................#.................#......#...#..#..#..#..#..#..#..#..# .............................................................#....................#...#...#..........................#.............
result:
ok res = 244063801
Test #50:
score: 0
Accepted
time: 923ms
memory: 271400kb
input:
536539457
output:
..........................................................................#...............#.............#.......#......#......#......#......#......#......#......#....#....#....# ..........................................................................#...............#.............#.......#......#.....
result:
ok res = 536539457
Test #51:
score: 0
Accepted
time: 890ms
memory: 271236kb
input:
462293418
output:
....................................................................................#..#..#......................#...................#.......#.......#......#....#...#...#...#..# ....................................................................................#..#..#......................#...........
result:
ok res = 462293418
Test #52:
score: 0
Accepted
time: 927ms
memory: 269068kb
input:
36920527
output:
....................................................................#........#.......#....#..............#........#........#.......#.......#.......#......#....#....#....#....#...# ....................................................................#........#.......#....#..............#........#........
result:
ok res = 36920527
Test #53:
score: 0
Accepted
time: 905ms
memory: 272260kb
input:
172808412
output:
.........................................................................#............#...#.......................#.................#........#..#..#..#..#..#..# .........................................................................#............#...#.......................#.................#.........
result:
ok res = 172808412
Test #54:
score: 0
Accepted
time: 934ms
memory: 271604kb
input:
702785565
output:
...........................................................#........................#..#..#.......................#......................#.............#...#...#...#..# ...........................................................#........................#..#..#.......................#....................
result:
ok res = 702785565
Test #55:
score: 0
Accepted
time: 888ms
memory: 271524kb
input:
364908069
output:
.............................................................#...............#....#...#...#.....................#..........#..........#.......#......#......#...#...#...# .............................................................#...............#....#...#...#.....................#..........#.........
result:
ok res = 364908069
Test #56:
score: 0
Accepted
time: 905ms
memory: 271620kb
input:
700033068
output:
............................................................#..........#.........#........#..........................#..........#..........#........#.......#....#....#..# ............................................................#..........#.........#........#..........................#..........#...
result:
ok res = 700033068
Test #57:
score: 0
Accepted
time: 899ms
memory: 271092kb
input:
971419570
output:
............................................................#................#....#...#...#...........................#..........#...#...#...#...#...#...#..#..#..#..#..# ............................................................#................#....#...#...#...........................#..........#...
result:
ok res = 971419570
Test #58:
score: 0
Accepted
time: 879ms
memory: 271744kb
input:
215988289
output:
...............................................................................................#..............#............#.........#.........#......#......#....#...#...#..#..#..#..# ...............................................................................................#..............#........
result:
ok res = 215988289
Test #59:
score: 0
Accepted
time: 896ms
memory: 271264kb
input:
233354450
output:
..................................................#.................#...#...#...#...#..#..#....................................#...............#...............#.......#.......#..# ..................................................#.................#...#...#...#...#..#..#................................
result:
ok res = 233354450
Test #60:
score: 0
Accepted
time: 891ms
memory: 269224kb
input:
460230232
output:
.....................................................#..................#..............#..#.................#........#......#......#...#...#...#...#...#...#...#..#..#..#..# .....................................................#..................#..............#..#.................#........#......#.....
result:
ok res = 460230232
Test #61:
score: 0
Accepted
time: 935ms
memory: 272132kb
input:
169672436
output:
............................................................................#..........#..#................#................#............#............#............#....#..#..#..# ............................................................................#..........#..#................#................
result:
ok res = 169672436
Test #62:
score: 0
Accepted
time: 910ms
memory: 272648kb
input:
116851312
output:
................................................................................#......#..#.............................#..........#....#....#....#....#....#..# ................................................................................#......#..#.............................#..........#....#.....
result:
ok res = 116851312
Test #63:
score: 0
Accepted
time: 864ms
memory: 272236kb
input:
654952096
output:
.......................................................................#.........#..#..#..#.................#.........#.........#......#...#...#..#..# .......................................................................#.........#..#..#..#.................#.........#.........#......#...#...#..#..#
result:
ok res = 654952096
Test #64:
score: 0
Accepted
time: 906ms
memory: 272220kb
input:
456784940
output:
...............................................................#..................#.......#......................#......................#........#........#....#....#....#...#...# ...............................................................#..................#.......#......................#..........
result:
ok res = 456784940
Test #65:
score: 0
Accepted
time: 904ms
memory: 269620kb
input:
903918017
output:
.....................................................................................#...#............................#..........#..........#........#.......#.......#...#..#..#..# .....................................................................................#...#............................#....
result:
ok res = 903918017
Test #66:
score: 0
Accepted
time: 862ms
memory: 269436kb
input:
242185681
output:
..................................................................#..................#....#..................#................#.........#.........#........#....#...#..#..#..#..#..# ..................................................................#..................#....#..................#............
result:
ok res = 242185681
Test #67:
score: 0
Accepted
time: 891ms
memory: 272140kb
input:
931841631
output:
......................................................#...........................#...#...#.........................#....................#..............#..........#........#...#..# ......................................................#...........................#...#...#.........................#.....
result:
ok res = 931841631
Test #68:
score: 0
Accepted
time: 888ms
memory: 272756kb
input:
705201940
output:
.....................................................................#....................#............#........#........#.......#....#...#...#...#...#...#...#..# .....................................................................#....................#............#........#........#.......#....#.....
result:
ok res = 705201940
Test #69:
score: 0
Accepted
time: 931ms
memory: 272112kb
input:
388071742
output:
....................................................................................#..#..#..................#...............#.............#.............#...#...#...#...#..#..# ....................................................................................#..#..#..................#................
result:
ok res = 388071742
Test #70:
score: 0
Accepted
time: 924ms
memory: 269732kb
input:
675160794
output:
.....................................................#....................................#......................#.............#.............#..........#....#..#..#..#..#..# .....................................................#....................................#......................#...............
result:
ok res = 675160794
Test #71:
score: 0
Accepted
time: 887ms
memory: 271024kb
input:
12451783
output:
...................................................................#......#...#..#..#..#..#.....................#..............#..............#.........#.......#...# ...................................................................#......#...#..#..#..#..#.....................#..............#.........
result:
ok res = 12451783
Test #72:
score: 0
Accepted
time: 899ms
memory: 270764kb
input:
275972627
output:
.......................................................................#.......#......#...#.................................#........#........#......#....#...#...#...#..# .......................................................................#.......#......#...#.................................#.......
result:
ok res = 275972627
Test #73:
score: 0
Accepted
time: 862ms
memory: 271408kb
input:
89200061
output:
...........................................................#.........#.......#.......#....#....................................#......#......#......#..#..# ...........................................................#.........#.......#.......#....#....................................#......#......#.....
result:
ok res = 89200061
Test #74:
score: 0
Accepted
time: 856ms
memory: 272220kb
input:
873057364
output:
................................................#................#.............#......#...#...............#..........#..........#..........#..........#..........#.........#.........# ................................................#................#.............#......#...#...............#.............
result:
ok res = 873057364
Test #75:
score: 0
Accepted
time: 901ms
memory: 271868kb
input:
469614007
output:
.................................................................................#..#..#.....................................#......................#.............#...# .................................................................................#..#..#.....................................#.........
result:
ok res = 469614007
Test #76:
score: 0
Accepted
time: 853ms
memory: 270948kb
input:
223340210
output:
............................................................................................#.................#............#..........#.......#.......#......#...#...#...#...#..#..# ............................................................................................#.................#...........
result:
ok res = 223340210
Test #77:
score: 0
Accepted
time: 870ms
memory: 272260kb
input:
822198166
output:
............................................................................#......#......#........................#........................#........#..#..#..#..#..#..#..#..# ............................................................................#......#......#........................#............
result:
ok res = 822198166
Test #78:
score: 0
Accepted
time: 887ms
memory: 272116kb
input:
455915168
output:
............................................................................#.........#...#.................................#...................#.........#.......#...#...#..#..# ............................................................................#.........#...#..................................
result:
ok res = 455915168
Test #79:
score: 0
Accepted
time: 892ms
memory: 272788kb
input:
194086925
output:
..................................................#...........................#.......#...#.........................#.............#..........#.........#......# ..................................................#...........................#.......#...#.........................#.............#............
result:
ok res = 194086925
Test #80:
score: 0
Accepted
time: 878ms
memory: 269160kb
input:
360828081
output:
.............................................................................#.........#..#.......................#...............#.........#.......#....#....#...#...#...#..# .............................................................................#.........#..#.......................#.............
result:
ok res = 360828081
Test #81:
score: 0
Accepted
time: 868ms
memory: 272680kb
input:
474052493
output:
........................................................................#.................#............................#.................#.............#........#........#.......#...# ........................................................................#.................#.............................
result:
ok res = 474052493