QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245268#7659. Highway Combinatoricsmshcherba#AC ✓2180ms44236kbC++202.5kb2023-11-09 20:15:182023-11-09 20:15:19

Judging History

你现在查看的是最新测评结果

  • [2023-11-09 20:15:19]
  • 评测
  • 测评结果:AC
  • 用时:2180ms
  • 内存:44236kb
  • [2023-11-09 20:15:18]
  • 提交

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