QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#245268 | #7659. Highway Combinatorics | mshcherba# | AC ✓ | 2180ms | 44236kb | C++20 | 2.5kb | 2023-11-09 20:15:18 | 2023-11-09 20:15:19 |
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, a, b) for(int i = (a) - 1; i >= (b); 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 = 1'000'000'007;
const int MAGIC = 1 << 17;
mt19937 rng;
void updAdd(int& x, int val)
{
x += val;
if (x >= mod)
x -= mod;
}
void updSub(int& x, int val)
{
x -= val;
if (x < 0)
x += 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 >>= 1;
}
return res;
}
int f(const vector<string>& s)
{
assert(SZ(s[0]) == SZ(s[1]));
vector dp(2, VI(2));
dp[1][1] = 1;
FOR(i, 0, SZ(s[0]))
{
vector ndp(2, VI(2));
FOR(j, 0, 2)
FOR(k, 0, 2)
{
int cur = dp[j][k];
bool b0 = s[0][i] == '#', b1 = s[1][i] == '#';
if (!b0 && !b1 && j && k)
updAdd(ndp[1][1], cur);
int p0 = j ^ 1, p1 = k ^ 1;
if ((p0 && b0) || (p1 && b1))
continue;
updAdd(ndp[b0 || p0][b1 || p1], cur);
}
dp = ndp;
}
return dp[1][1];
}
int rand(int a, int b)
{
return a + rng() % (b - a);
}
vector<string> randomVector()
{
int n = 2 * rand(30, 50);
vector<string> vec(2, string(n, '.'));
for (string& s : vec)
{
int k = rand(3, 7);
FOR(i, 0, k)
{
int j = rand(0, n - 1);
if (s[j] == '.' && s[j + 1] == '.')
s[j] = s[j + 1] = '#';
}
}
return vec;
}
vector<string> prk1[MAGIC];
unordered_map<int, int> mp;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
if (n == 0)
{
cout << "##.\n.##\n";
return 0;
}
int cnt0 = 0;
FOR(i, 0, MAGIC)
{
prk1[i] = randomVector();
int c = f(prk1[i]);
if (c != 0)
mp[c] = i;
else
cnt0++;
}
cerr << SZ(mp) << " " << MAGIC << "\n";
while (true)
{
vector<string> prk2 = randomVector();
int c = f(prk2);
if (c == 0)
continue;
int d = mult(n, binpow(c, mod - 2));
if (mp.count(d))
{
vector<string> ans(2);
int i = mp[d];
FOR(j, 0, 2)
{
ans[j] = prk1[i][j] + "#" + prk2[j];
cout << ans[j] << "\n";
}
cerr << (db)clock() / CLOCKS_PER_SEC << endl;
assert(f(ans) == n);
return 0;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 771ms
memory: 44220kb
input:
10
output:
........................##............................##.##...#..##...##............##..................................##...........##.. .##............................##.......####...............##.#.................##.....##.......##..........................##...........
result:
ok res = 10
Test #2:
score: 0
Accepted
time: 793ms
memory: 44140kb
input:
27
output:
......##............................##................##...............##................##...###.........##.............##...................##.............##.............##......... .##..............................................##..........##...............................#........................
result:
ok res = 27
Test #3:
score: 0
Accepted
time: 738ms
memory: 44224kb
input:
1000000006
output:
....................................##................##.......##.......................###...........................................##......##............... .##..........##.....................................##..........................##......#..####.....##.................##.............##.......
result:
ok res = 1000000006
Test #4:
score: 0
Accepted
time: 784ms
memory: 44156kb
input:
1000000000
output:
...................##..........####..........##...............##..........#.................##.........##.............##................##. ...##......##..##.........................................................#.......................................####.....................
result:
ok res = 1000000000
Test #5:
score: 0
Accepted
time: 0ms
memory: 6484kb
input:
0
output:
##. .##
result:
ok res = 0
Test #6:
score: 0
Accepted
time: 1115ms
memory: 44144kb
input:
1
output:
.............##...........##.......................##.............................................#........................##..................##..........##......................##.......... ......................##..##...##............##...................................................#.##.........
result:
ok res = 1
Test #7:
score: 0
Accepted
time: 977ms
memory: 44124kb
input:
7
output:
.##......................##................................................##..##.............###.##............................................##...................##..##.....##....... .....##............................................##..........................##..##...........#....................
result:
ok res = 7
Test #8:
score: 0
Accepted
time: 830ms
memory: 44144kb
input:
144000001
output:
.......................##.....................##....##...##..........##...##..............#.....##......................................................##..........##....................... ...##.....................##................................................##............#......................
result:
ok res = 144000001
Test #9:
score: 0
Accepted
time: 948ms
memory: 44156kb
input:
46750697
output:
.##.............................................##.................................##.........#..............##...............##........##.......##........................##.............. ........##...##......................................##.........##............................#......##.##.........
result:
ok res = 46750697
Test #10:
score: 0
Accepted
time: 980ms
memory: 44216kb
input:
12345678
output:
.##........................##.................................##................#................................##..............##.........##....####. ....................##.................................##.##....##..............#.##.....##........##........##........................................
result:
ok res = 12345678
Test #11:
score: 0
Accepted
time: 773ms
memory: 44188kb
input:
102334155
output:
......................................##..................####..........................#.................####..........##............##..................................##............. ##...................##.........................................................##...##.#............................
result:
ok res = 102334155
Test #12:
score: 0
Accepted
time: 733ms
memory: 44092kb
input:
165580141
output:
.....##..##....##.....................................................##......#......##.........................##...##......##.............................. ...##....................##..............##........##............##...........#......####........................................................
result:
ok res = 165580141
Test #13:
score: 0
Accepted
time: 730ms
memory: 44124kb
input:
8390086
output:
..........##.##....##.##.............##.........................#.................................##.##.....##........................... ....##...................##....##....##.....##...........##.....#....................................####......................##...##...
result:
ok res = 8390086
Test #14:
score: 0
Accepted
time: 842ms
memory: 44212kb
input:
210345902
output:
...................##..........................................##.............###.....................................##..........##.......................##.....##......... ...##.................##......................##.##...........................###................................##...##.........
result:
ok res = 210345902
Test #15:
score: 0
Accepted
time: 894ms
memory: 44220kb
input:
755204270
output:
...........##.......................##.....................##...#.##..........................##....................................... ................................##.......##.##..................#.............##...##.....................##...........................
result:
ok res = 755204270
Test #16:
score: 0
Accepted
time: 945ms
memory: 44152kb
input:
349361645
output:
.............................................................##....##.......##..#....................##.........................##............................. ...............##..................##........................##.................#.........................##.##................................
result:
ok res = 349361645
Test #17:
score: 0
Accepted
time: 730ms
memory: 44148kb
input:
529309711
output:
...........................##......................................##..##...........##..###..##...............##.................................##.....................##.##.. .............##..........................##......................##.......................#.............##.............##......
result:
ok res = 529309711
Test #18:
score: 0
Accepted
time: 906ms
memory: 44236kb
input:
878671356
output:
.##..........................................##.......##........#.................##...........##........................##.............................. ...........##......................##........##.....##..........#...................##..##...................................##..............##......
result:
ok res = 878671356
Test #19:
score: 0
Accepted
time: 897ms
memory: 44184kb
input:
141851555
output:
..............##.............##.......................##...........##...............##............#.................................##..##..................##....##............................... ...........................##........##.............##...............##........................##.#........
result:
ok res = 141851555
Test #20:
score: 0
Accepted
time: 774ms
memory: 44124kb
input:
245606600
output:
......................##......##..##...................##...............##..................#..............##............##................................##.....##..................... ............................................##.......................................##.....#........................
result:
ok res = 245606600
Test #21:
score: 0
Accepted
time: 1369ms
memory: 44236kb
input:
387458156
output:
..................................##...............##..##.................................##....#..####.........##............##............................................................. .............................................##......##......................##.........####....#....##..........
result:
ok res = 387458156
Test #22:
score: 0
Accepted
time: 736ms
memory: 44144kb
input:
447800885
output:
....................##..............................##..##......#...............##...........##....##................##.......##............................... ......##...##...##...................##.....##..............##..#.##.........................##........................##.........##...........
result:
ok res = 447800885
Test #23:
score: 0
Accepted
time: 1164ms
memory: 44164kb
input:
981661739
output:
..##.......................##.......##....................####......##..........................#..............................##..##................##...................##............##...##.... ............................................................##......##...##.............##......#..........
result:
ok res = 981661739
Test #24:
score: 0
Accepted
time: 927ms
memory: 44136kb
input:
999999929
output:
.......##.......##.....##............##.....................................................#...##...............................................##..................##................ ..##..........................##.............................##.............................#..................##......
result:
ok res = 999999929
Test #25:
score: 0
Accepted
time: 782ms
memory: 44140kb
input:
35345813
output:
....##.......................##.....##................................................##..#.........##.................................##....##............................................ .................##....................................##..........##.......##......##....#........................
result:
ok res = 35345813
Test #26:
score: 0
Accepted
time: 902ms
memory: 44144kb
input:
33810803
output:
.....##................##....................................................##..##..##.....#............##...........##.............................##.##........................##..... .............................####...##......................................................#..............##..##....
result:
ok res = 33810803
Test #27:
score: 0
Accepted
time: 1321ms
memory: 44156kb
input:
966289935
output:
...........##...............................##.........##...................##.##.#.............................##......................##......................####...##...##..... ................##...##..##...............................##.##........##.........#........................................
result:
ok res = 966289935
Test #28:
score: 0
Accepted
time: 857ms
memory: 44232kb
input:
29521716
output:
......##.......................................##............##.............#.....##........................................................................##.......##.... .............##..........##............................##...................#..............##..............##.......##.##..........
result:
ok res = 29521716
Test #29:
score: 0
Accepted
time: 856ms
memory: 44136kb
input:
64472472
output:
.............................................##.##...##.................................##..#....##..............................##........##............................................ ........##................................##................................................#........................
result:
ok res = 64472472
Test #30:
score: 0
Accepted
time: 1397ms
memory: 44108kb
input:
158427805
output:
....##................##....##........................................##..................#..............##......##.............................................##.##...................... ..............##........##..##......................................##..............##....#....##....##............
result:
ok res = 158427805
Test #31:
score: 0
Accepted
time: 1682ms
memory: 44144kb
input:
476648214
output:
............##........................##...........##................##.............#......##.................##.....##.....................##......................................... .......................##.............##.................................##.........#.................##...............
result:
ok res = 476648214
Test #32:
score: 0
Accepted
time: 763ms
memory: 44224kb
input:
460753020
output:
..............................##..........................##...##.........##......................#..................##......................##..##.............................##......... .............##..........##...............##.........##.............................##............#................
result:
ok res = 460753020
Test #33:
score: 0
Accepted
time: 755ms
memory: 44120kb
input:
846275927
output:
..##..........................................##..##................##............#............................##.............##................. ................##.....##....................................##...................###.........##......................##.................##......
result:
ok res = 846275927
Test #34:
score: 0
Accepted
time: 1336ms
memory: 44188kb
input:
436044186
output:
...................##.##.....................................................##.......##..#..............##...........##...........................##....................##............ ........##.........##.......................##.........##...........................##....#..........##...........##...
result:
ok res = 436044186
Test #35:
score: 0
Accepted
time: 778ms
memory: 44184kb
input:
4714726
output:
...##......................##...........##...................##.......................#......##......##.................................##....##....##......... .....##.................##.....................................##.....................#..........##..........................##..##............
result:
ok res = 4714726
Test #36:
score: 0
Accepted
time: 808ms
memory: 44124kb
input:
405106993
output:
..............................##........................##......................##......#................................................##...........##..........##.............##...... .............##......................##......##.........................................#...##.......................
result:
ok res = 405106993
Test #37:
score: 0
Accepted
time: 1805ms
memory: 44144kb
input:
395136214
output:
##.............##.....##..................##.....................##.......##..................#......##........##.......##........................##...##...................##..... ...................................##.......##.........##....##....................##.........#.......................##...
result:
ok res = 395136214
Test #38:
score: 0
Accepted
time: 821ms
memory: 44144kb
input:
318600029
output:
.................................##................................##.....##..................#............##.................................##.........##...................................... ....##..........##......................##....................................................#.##...........
result:
ok res = 318600029
Test #39:
score: 0
Accepted
time: 730ms
memory: 44192kb
input:
446626687
output:
.##.##.........##.................................##..................##....................#......................##......................####...................................##....... .##...................##..................##................##......##......................#......................
result:
ok res = 446626687
Test #40:
score: 0
Accepted
time: 722ms
memory: 44172kb
input:
152602867
output:
..##..........................................##......................................##..........#.##..........##.........................................##................ ............................................####..##............................##................#................##..##........
result:
ok res = 152602867
Test #41:
score: 0
Accepted
time: 1125ms
memory: 44152kb
input:
989466381
output:
..............................................##....................................##.......##.#.##..................##.....##......##...............##............................... ..................##...........##...........##...##.............................................#......................
result:
ok res = 989466381
Test #42:
score: 0
Accepted
time: 766ms
memory: 44192kb
input:
936862096
output:
..##..............................................##.....##...##....#.............##...##.##.##................##.............................................. ...............................##...............................##..#......................................##......##..........................
result:
ok res = 936862096
Test #43:
score: 0
Accepted
time: 864ms
memory: 44128kb
input:
716629682
output:
............................................##..................................##......#..........##..........##........................................##.............. ##......................................##.....##.............##..............##........#.##.....##..................................
result:
ok res = 716629682
Test #44:
score: 0
Accepted
time: 997ms
memory: 44124kb
input:
777283759
output:
......##........##.................##.......##.......##....................##.....#...............................##.....##..............##......##.........##.......##.. ............##...............##.##................................................#......####......##................................
result:
ok res = 777283759
Test #45:
score: 0
Accepted
time: 1446ms
memory: 44140kb
input:
791644428
output:
...........................##..................##....##........##.....................#....................##........................##..##.##................##. ##...................................##......................................##.......#.......##.......##.......................##...........
result:
ok res = 791644428
Test #46:
score: 0
Accepted
time: 1199ms
memory: 44128kb
input:
653877186
output:
...............##.........##.......................##..........####.......................#.................................##....................................##....... ..........................##...##...............##....................##...##.............#......##....##...................##.....
result:
ok res = 653877186
Test #47:
score: 0
Accepted
time: 964ms
memory: 44192kb
input:
927194288
output:
.................##...........##............##....................................#...................##...........##.........................................................##..... ..........##.......##.........##....................................##......##....###.............##.....................
result:
ok res = 927194288
Test #48:
score: 0
Accepted
time: 2180ms
memory: 44196kb
input:
926281794
output:
.##....##.......##...##...............##........................................................#..............##....##.............##...............................##........ ................................##...............................##.......##....................#..............................
result:
ok res = 926281794
Test #49:
score: 0
Accepted
time: 717ms
memory: 44156kb
input:
244063801
output:
...##..##........................................##.........##..............##.##.#...............................##...............##...........##................. ................##...................##.............##.................##.##......#....##.............................##......##...........
result:
ok res = 244063801
Test #50:
score: 0
Accepted
time: 750ms
memory: 44160kb
input:
536539457
output:
..####............................##............................................................#..............................##......................##.......##......... ..................##.............................................................##.......##....#.............##...................
result:
ok res = 536539457
Test #51:
score: 0
Accepted
time: 883ms
memory: 44228kb
input:
462293418
output:
........................##...............................................................####.#.....##...##.........................................##....##............. ................##................................................................##..........###.......................##...........
result:
ok res = 462293418
Test #52:
score: 0
Accepted
time: 731ms
memory: 44188kb
input:
36920527
output:
.##....................##............##...................................##....................###...##......##........##.....................##...................... ............##..............................................................####................#........##..........##.##...##........
result:
ok res = 36920527
Test #53:
score: 0
Accepted
time: 1294ms
memory: 44144kb
input:
172808412
output:
##.........................................##..##...................###...................##....................................##... ..........##.........####.........##................................#..##............##.##...........................................
result:
ok res = 172808412
Test #54:
score: 0
Accepted
time: 728ms
memory: 44124kb
input:
702785565
output:
....................##...........####...........##.......................##...#......##..................##..................................##.. ####.##.........##............................................##..............#....##..........##..............................................##
result:
ok res = 702785565
Test #55:
score: 0
Accepted
time: 755ms
memory: 44120kb
input:
364908069
output:
...........................##................##.....##........................##..................#.............####...##..............##........................ .....................................................................##...........##...##.........#...##......##............##...............
result:
ok res = 364908069
Test #56:
score: 0
Accepted
time: 1001ms
memory: 44172kb
input:
700033068
output:
..............##..............................................##..........###.............##..............##.......................................##............ .##........................##..............##...............................#..........##.....##.............................................
result:
ok res = 700033068
Test #57:
score: 0
Accepted
time: 770ms
memory: 44236kb
input:
971419570
output:
...................##........##...........................................##......#..........................##........##......##................##.... .........................................##.......................##....##........#........................................##........##..........##....
result:
ok res = 971419570
Test #58:
score: 0
Accepted
time: 1721ms
memory: 44224kb
input:
215988289
output:
..##...................##.................##..................##.####.................#................##.....................##..##....................####................... ........##....##.##...................##...............##.............................#.............##.........................
result:
ok res = 215988289
Test #59:
score: 0
Accepted
time: 811ms
memory: 44160kb
input:
233354450
output:
.....##..................##........##...##.....##..##.................#.....................##........##.................##........##....##............................ ......................##........##...##.............................###..........................##...##...............................
result:
ok res = 233354450
Test #60:
score: 0
Accepted
time: 1018ms
memory: 44188kb
input:
460230232
output:
.........##........................##..................##.......##..........##..................#.....................##...##...##...##..............................................##.##....... ........................##..............##........##.........##.................................#............
result:
ok res = 460230232
Test #61:
score: 0
Accepted
time: 701ms
memory: 44228kb
input:
169672436
output:
.................................##....####.......................#............##.....##......................##.##......##............................##........ ##........................##.....##..........................##...#.....................##.............................##......##............
result:
ok res = 169672436
Test #62:
score: 0
Accepted
time: 790ms
memory: 44172kb
input:
116851312
output:
....##...................##.......................................##................#......##............................................................##...........##.##.......... .................##...............................##.......##..##...............##..#....................................
result:
ok res = 116851312
Test #63:
score: 0
Accepted
time: 766ms
memory: 44144kb
input:
654952096
output:
.............##...................................##..........##...........................##.###..................................##........##......##.............................. ..................##..........##...##....................................................##...#..........................
result:
ok res = 654952096
Test #64:
score: 0
Accepted
time: 760ms
memory: 44184kb
input:
456784940
output:
..##......................................##.......##.....................................#.........##....##......................##......##................... ............................................##..........####........##..................###...................##..##................##.........
result:
ok res = 456784940
Test #65:
score: 0
Accepted
time: 1483ms
memory: 44188kb
input:
903918017
output:
.......##.......##.........................##.####.......##.###.....####.....##..........##.............................. ........................................##........##...####.#.............##....##................##.......##............
result:
ok res = 903918017
Test #66:
score: 0
Accepted
time: 731ms
memory: 44124kb
input:
242185681
output:
.........##.##......##...........................##.............................##....#..........................................##.......##.............................####.......... ......................................####....................##..##..................#.......##.......................
result:
ok res = 242185681
Test #67:
score: 0
Accepted
time: 767ms
memory: 44192kb
input:
931841631
output:
........##......................##.........##.............................#............##..................##............................##.......####..........##. .##.......##.................................##......................####.#.....................................##.........##.........##...
result:
ok res = 931841631
Test #68:
score: 0
Accepted
time: 1097ms
memory: 44152kb
input:
705201940
output:
.......##........................................##.................##...##.............#..........................##...................................####.##...... .......##...##................................................##...............##.......#....................................##......#...
result:
ok res = 705201940
Test #69:
score: 0
Accepted
time: 830ms
memory: 44224kb
input:
388071742
output:
................##...##...........................................##..............#.##.......................................................##.##... ...................##...................##.......##.##..........................###......................##.........##.##.......................##...
result:
ok res = 388071742
Test #70:
score: 0
Accepted
time: 735ms
memory: 44152kb
input:
675160794
output:
...............................................##.......##................##....##............#..##......................................................##.........##................. ............##........##....##.......##................................##.....................#.......##.........##....
result:
ok res = 675160794
Test #71:
score: 0
Accepted
time: 736ms
memory: 44148kb
input:
12451783
output:
..............##.........##...##.....##...........##.....##.....#...........##.............##...............................##............................... .....##........................................##.....##........#.....##....##..##.......##.........................##.......................#...
result:
ok res = 12451783
Test #72:
score: 0
Accepted
time: 1109ms
memory: 44160kb
input:
275972627
output:
......##.............##...##......##..................##..........................#........................##...##...........##.......####..................................... .................##...........##.....##...##......................................#.............................##.........#...
result:
ok res = 275972627
Test #73:
score: 0
Accepted
time: 928ms
memory: 44216kb
input:
89200061
output:
.....................................##................##.......##..........#......##...............##..................................................................##... ..........##..................................##.............##.............#.......................##...........................
result:
ok res = 89200061
Test #74:
score: 0
Accepted
time: 791ms
memory: 44160kb
input:
873057364
output:
.............................##...##....##.........##...................#..................##..............................##.....................##....... ...........##.......##.......................................####.......#............##.......................##......##...........................
result:
ok res = 873057364
Test #75:
score: 0
Accepted
time: 912ms
memory: 44212kb
input:
469614007
output:
..##......................##..........##.......##...........................................#..##...............................................##..............##...##................ ................##................................##.........##..............##.............#..##....##................
result:
ok res = 469614007
Test #76:
score: 0
Accepted
time: 716ms
memory: 44192kb
input:
223340210
output:
...........................##..........####.........................##.....##...........#.....##........................................##...........##.................................... ...................................##.......##....................................##....#..........................
result:
ok res = 223340210
Test #77:
score: 0
Accepted
time: 782ms
memory: 44212kb
input:
822198166
output:
........##...................................................................##...........#.##.........##......##.......................##.......##..##.................. ................................##.................................##................##...#.............................##......##...
result:
ok res = 822198166
Test #78:
score: 0
Accepted
time: 952ms
memory: 44188kb
input:
455915168
output:
...####........................##.......................................##....#....##.....##...............##...................##.......##.... ...............................................##..##.........................#..............##.........##.##..................................
result:
ok res = 455915168
Test #79:
score: 0
Accepted
time: 1985ms
memory: 44124kb
input:
194086925
output:
....##.....................................................##......................##.##......#........##.....................####..................................##.##........................ ................##..............##....##............................##...##...................#..............
result:
ok res = 194086925
Test #80:
score: 0
Accepted
time: 865ms
memory: 44140kb
input:
360828081
output:
......................##...................##.....##......................##.##.##................#...............................##....##.......................##.........##...............##.... ...........##..............................####.##................................................#........
result:
ok res = 360828081
Test #81:
score: 0
Accepted
time: 779ms
memory: 44172kb
input:
474052493
output:
......##..##...................................................##...............#............................##..........##...##..................................... .................................##.....##......................................#.....##.....##..................##......................
result:
ok res = 474052493