QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#233241#7659. Highway CombinatoricsValenciaTravis#AC ✓436ms73748kbC++202.2kb2023-10-31 15:32:202023-10-31 15:32:20

Judging History

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

  • [2023-10-31 15:32:20]
  • 评测
  • 测评结果:AC
  • 用时:436ms
  • 内存:73748kb
  • [2023-10-31 15:32:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define MAXN 105
#define ll long long
#define int long long
const ll mod = 1e9 + 7;
int n;
ll f[105];
vector<char> s;
vector<int> v, from;
unordered_map<int, int> mp;
ll qpow(ll a, ll b){
    ll ret = 1;
    while(b){
        if(b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
void init(){
    queue<pair<int, int>> q;
    q.push({1, 0});
    int cnt = 1;
    mp[1] = 1;
    v.push_back(1); from.push_back(0);
    while(!q.empty() && cnt < 1e6){
        auto [x, t] = q.front();
        q.pop();
        for(int i=2;i<100-t;i++){
            int x1 = ((ll)x * f[i])  % mod;
            int t1 = (t+i+1);
            if(mp[x1]) continue;
            mp[x1] = ++cnt;
            v.push_back(x1), from.push_back(i);
            if(t1 != 100) q.push({x1, t1});
        }
    }
    // printf("cnt = %d\n", cnt);
}
void print(int x){
    // printf("x = %d\n", x);
    int tmp = x;
    ll check = 1;
    while(tmp != 1){
        if(s.size()) s.push_back('#');
        int id = mp[tmp] - 1;
        for(int i=1;i<=from[id];i++) s.push_back('.');
        check = check * f[from[id]] % mod;
        tmp = (ll) tmp * qpow(f[from[id]], mod-2) % mod;
    }
    tmp = n * qpow(x, mod-2) % mod;
    while(tmp != 1){
        if(s.size()) s.push_back('#');
        int id = mp[tmp] - 1;
        // printf("tmp = %d, id = %d, from = %d\n", tmp, id, from[id]);
        for(int i=1;i<=from[id];i++) s.push_back('.');
        check = check * f[from[id]] % mod;
        tmp = (ll) tmp * qpow(f[from[id]], mod-2) % mod;
    }
    // if(check != n) assert(0);
    // if(s.size() > 200) assert(0);
    for(auto c : s) putchar(c); putchar('\n');
    for(auto c : s) putchar(c); putchar('\n');
}
signed main(){
    f[0] = f[1] = 1;
    for(int i=2;i<=100;i++) f[i] = (f[i-1] + f[i-2]) % mod;//, printf("%lld\n", f[i]);
    cin>>n;
    if(n == 0){
        puts("##.\n.##");
        return 0;
    }else if(n == 1){
        puts(".\n.");
        return 0;
    }
    init();
    for(auto x : v){
        int tmp = (ll)n * qpow(x, mod-2) % mod;
        int &X = mp[tmp];
        if(X) return print(x), 0;
    }
    assert(0);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 337ms
memory: 72896kb

input:

10

output:

....#..
....#..

result:

ok res = 10

Test #2:

score: 0
Accepted
time: 326ms
memory: 73160kb

input:

27

output:

...#...#...
...#...#...

result:

ok res = 27

Test #3:

score: 0
Accepted
time: 393ms
memory: 73068kb

input:

1000000006

output:

.....................................#.................................#...............................#..............................#.........................#...#..#..
.....................................#.................................#...............................#............................

result:

ok res = 1000000006

Test #4:

score: 0
Accepted
time: 378ms
memory: 72820kb

input:

1000000000

output:

.....................................#.................................#..#...............................#..............................#.........................#.......#..
.....................................#.................................#..#...............................#.....................

result:

ok res = 1000000000

Test #5:

score: 0
Accepted
time: 0ms
memory: 3376kb

input:

0

output:

##.
.##

result:

ok res = 0

Test #6:

score: 0
Accepted
time: 0ms
memory: 3440kb

input:

1

output:

.
.

result:

ok res = 1

Test #7:

score: 0
Accepted
time: 369ms
memory: 73372kb

input:

7

output:

...............................................................#..............................#......................#...............#.......#.......#..
...............................................................#..............................#......................#...............#.......#........

result:

ok res = 7

Test #8:

score: 0
Accepted
time: 367ms
memory: 72824kb

input:

144000001

output:

.................................................................#.........#...#........................#.......................#...................#.................#....#..
.................................................................#.........#...#........................#.......................

result:

ok res = 144000001

Test #9:

score: 0
Accepted
time: 361ms
memory: 73020kb

input:

46750697

output:

................................................................#..................................#................................................#......................#.................#.....#...
................................................................#..................................#...

result:

ok res = 46750697

Test #10:

score: 0
Accepted
time: 381ms
memory: 73076kb

input:

12345678

output:

..........................................#.................................#...........#.......................#......................#..............#..............#.............
..........................................#.................................#...........#.......................#..........

result:

ok res = 12345678

Test #11:

score: 0
Accepted
time: 393ms
memory: 72940kb

input:

102334155

output:

.......................................
.......................................

result:

ok res = 102334155

Test #12:

score: 0
Accepted
time: 336ms
memory: 73500kb

input:

165580141

output:

........................................
........................................

result:

ok res = 165580141

Test #13:

score: 0
Accepted
time: 363ms
memory: 73500kb

input:

8390086

output:

.......................................................................
.......................................................................

result:

ok res = 8390086

Test #14:

score: 0
Accepted
time: 362ms
memory: 72848kb

input:

210345902

output:

.........................................................................................
.........................................................................................

result:

ok res = 210345902

Test #15:

score: 0
Accepted
time: 340ms
memory: 72988kb

input:

755204270

output:

..........................................................................................
..........................................................................................

result:

ok res = 755204270

Test #16:

score: 0
Accepted
time: 361ms
memory: 72820kb

input:

349361645

output:

.....................................................................#...#...............................#.....................#...................#..................#...#..
.....................................................................#...#...............................#.......................

result:

ok res = 349361645

Test #17:

score: 0
Accepted
time: 338ms
memory: 72952kb

input:

529309711

output:

.......................................................#....................#..#.............................#..........................#..............#..............#......#..
.......................................................#....................#..#.............................#................

result:

ok res = 529309711

Test #18:

score: 0
Accepted
time: 339ms
memory: 72984kb

input:

878671356

output:

........................................#.................................#..#..............................................#..............#...........#..........#...#..
........................................#.................................#..#..............................................#........

result:

ok res = 878671356

Test #19:

score: 0
Accepted
time: 366ms
memory: 72820kb

input:

141851555

output:

...................................................................................................#...................................................................................................
...................................................................................................#...

result:

ok res = 141851555

Test #20:

score: 0
Accepted
time: 362ms
memory: 73416kb

input:

245606600

output:

..........................................................#.................................#.....................#.....................#...................#..................#....#..
..........................................................#.................................#.....................#....

result:

ok res = 245606600

Test #21:

score: 0
Accepted
time: 316ms
memory: 72892kb

input:

387458156

output:

................................................#................................#..................................................#................#................#............
................................................#................................#.........................................

result:

ok res = 387458156

Test #22:

score: 0
Accepted
time: 332ms
memory: 73304kb

input:

447800885

output:

....................................................#..........................#................................#............................#..............#...........#....#..
....................................................#..........................#................................#.............

result:

ok res = 447800885

Test #23:

score: 0
Accepted
time: 312ms
memory: 72908kb

input:

981661739

output:

..........................................#...#................................................#......#......#.....#.....
..........................................#...#................................................#......#......#.....#.....

result:

ok res = 981661739

Test #24:

score: 0
Accepted
time: 329ms
memory: 72856kb

input:

999999929

output:

...............................................................#...........................#..........................#......#......
...............................................................#...........................#..........................#......#......

result:

ok res = 999999929

Test #25:

score: 0
Accepted
time: 333ms
memory: 72920kb

input:

35345813

output:

.........................................#..............#.............................#........................#......................#.......#.......#..
.........................................#..............#.............................#........................#......................#.......#......

result:

ok res = 35345813

Test #26:

score: 0
Accepted
time: 436ms
memory: 72932kb

input:

33810803

output:

.....................................#....................................#............#....#..#..........................#......................#.................#.............#.....#..
.....................................#....................................#............#....#..#....................

result:

ok res = 33810803

Test #27:

score: 0
Accepted
time: 338ms
memory: 72916kb

input:

966289935

output:

..................................#.......................#..............................#...........................#...................#.........#....#..
..................................#.......................#..............................#...........................#...................#.........

result:

ok res = 966289935

Test #28:

score: 0
Accepted
time: 383ms
memory: 72892kb

input:

29521716

output:

................................................................#....................#.........#..............................................#.....................#................#......#.....
................................................................#....................#.........#............

result:

ok res = 29521716

Test #29:

score: 0
Accepted
time: 369ms
memory: 72752kb

input:

64472472

output:

......................................................#................................#...#.......................................#.....................#...........#..........#........
......................................................#................................#...#.........................

result:

ok res = 64472472

Test #30:

score: 0
Accepted
time: 363ms
memory: 72980kb

input:

158427805

output:

.....................................#........................#...........#............................#.........................#....................#............#......#..
.....................................#........................#...........#............................#.........................

result:

ok res = 158427805

Test #31:

score: 0
Accepted
time: 340ms
memory: 73280kb

input:

476648214

output:

........................................................#...........#......#....#.........................#.................#............#...........#........#..
........................................................#...........#......#....#.........................#.................#............#...

result:

ok res = 476648214

Test #32:

score: 0
Accepted
time: 323ms
memory: 73124kb

input:

460753020

output:

.........................................................#...........#..............................#...........................#..........................#.......#....
.........................................................#...........#..............................#...........................#.....

result:

ok res = 460753020

Test #33:

score: 0
Accepted
time: 343ms
memory: 72856kb

input:

846275927

output:

...............................................#...................#....................................#......................#.................#............#........
...............................................#...................#....................................#......................#.......

result:

ok res = 846275927

Test #34:

score: 0
Accepted
time: 308ms
memory: 72816kb

input:

436044186

output:

.............................................#.......#...#................................#.....................#.................#.........#.......#..
.............................................#.......#...#................................#.....................#.................#.........#..........

result:

ok res = 436044186

Test #35:

score: 0
Accepted
time: 305ms
memory: 72928kb

input:

4714726

output:

...........................................#..#.....................................................#.................#......#......#...#..
...........................................#..#.....................................................#.................#......#......#...#..

result:

ok res = 4714726

Test #36:

score: 0
Accepted
time: 289ms
memory: 72904kb

input:

405106993

output:

.....................................................#.......#..#..............................#........................#....................#........#........#..
.....................................................#.......#..#..............................#........................#...................

result:

ok res = 405106993

Test #37:

score: 0
Accepted
time: 314ms
memory: 73100kb

input:

395136214

output:

.................................................#.............................................#..#.........................#........................#.................#............#........#..
.................................................#.............................................#..#...........

result:

ok res = 395136214

Test #38:

score: 0
Accepted
time: 347ms
memory: 72908kb

input:

318600029

output:

.........................................................................#................#...#...#..........................................#.................#................#......#......#..
.........................................................................#................#...#...#..........

result:

ok res = 318600029

Test #39:

score: 0
Accepted
time: 330ms
memory: 73020kb

input:

446626687

output:

...........................................................................#.....................#............................................#..........................................#......
...........................................................................#.....................#............

result:

ok res = 446626687

Test #40:

score: 0
Accepted
time: 284ms
memory: 72764kb

input:

152602867

output:

........................................................#...........................#...#.............................#....................#..............#..............#..............
........................................................#...........................#...#.............................

result:

ok res = 152602867

Test #41:

score: 0
Accepted
time: 283ms
memory: 72996kb

input:

989466381

output:

...........................................#......#....#........................#......................#.....................#............#......#..
...........................................#......#....#........................#......................#.....................#............#......#..

result:

ok res = 989466381

Test #42:

score: 0
Accepted
time: 305ms
memory: 72908kb

input:

936862096

output:

...........................#.....#.......................................#.................#.............#............#...........
...........................#.....#.......................................#.................#.............#............#...........

result:

ok res = 936862096

Test #43:

score: 0
Accepted
time: 287ms
memory: 72948kb

input:

716629682

output:

.......................................................#.........................................#.............................................#...........#...........#..........#.......#..
.......................................................#.........................................#...............

result:

ok res = 716629682

Test #44:

score: 0
Accepted
time: 343ms
memory: 72832kb

input:

777283759

output:

.......................................................#.......................#................#........................................................#................#...........#.......#..
.......................................................#.......................#................#............

result:

ok res = 777283759

Test #45:

score: 0
Accepted
time: 298ms
memory: 72948kb

input:

791644428

output:

.......................................................................#....#.........................#.....................#............#....#....#..
.......................................................................#....#.........................#.....................#............#....#....#..

result:

ok res = 791644428

Test #46:

score: 0
Accepted
time: 301ms
memory: 73020kb

input:

653877186

output:

....................................#................................#........#.............................#.....................#....................#..............#........#..
....................................#................................#........#.............................#...............

result:

ok res = 653877186

Test #47:

score: 0
Accepted
time: 276ms
memory: 72944kb

input:

927194288

output:

............................................#..............................#.............................#...........................#.....#..
............................................#..............................#.............................#...........................#.....#..

result:

ok res = 927194288

Test #48:

score: 0
Accepted
time: 275ms
memory: 72932kb

input:

926281794

output:

..............................................................#...........................#...#...........................#...........................#...................#...............#....#..
..............................................................#...........................#...#.............

result:

ok res = 926281794

Test #49:

score: 0
Accepted
time: 246ms
memory: 72808kb

input:

244063801

output:

.............................................................#.....#...#..........................#....................#.................#...........#......#..
.............................................................#.....#...#..........................#....................#.................#.....

result:

ok res = 244063801

Test #50:

score: 0
Accepted
time: 308ms
memory: 72944kb

input:

536539457

output:

..................................#......................#.....#........................................#............................#...........#......#.....#..
..................................#......................#.....#........................................#............................#.......

result:

ok res = 536539457

Test #51:

score: 0
Accepted
time: 292ms
memory: 73032kb

input:

462293418

output:

...................................................#......................................#...#...............................#.....................#..................#............#....#..
...................................................#......................................#...#...................

result:

ok res = 462293418

Test #52:

score: 0
Accepted
time: 307ms
memory: 72940kb

input:

36920527

output:

.................................................#...................................#..#..........................................#..............#.............#.............#.....#..
.................................................#...................................#..#..............................

result:

ok res = 36920527

Test #53:

score: 0
Accepted
time: 323ms
memory: 73020kb

input:

172808412

output:

.........................................................................#.....#...#.......................#.................#............#........#.....
.........................................................................#.....#...#.......................#.................#............#..........

result:

ok res = 172808412

Test #54:

score: 0
Accepted
time: 333ms
memory: 73036kb

input:

702785565

output:

................................................#..................#...#..............................#.....................#................#................#............
................................................#..................#...#..............................#.....................#......

result:

ok res = 702785565

Test #55:

score: 0
Accepted
time: 338ms
memory: 73696kb

input:

364908069

output:

..................................................................#....................#.......................#.......................#.....................#..............#......#..
..................................................................#....................#.......................#........

result:

ok res = 364908069

Test #56:

score: 0
Accepted
time: 319ms
memory: 72968kb

input:

700033068

output:

..............................................................#....................#...........#........................................................#...............#............#.....#..#..
..............................................................#....................#...........#.............

result:

ok res = 700033068

Test #57:

score: 0
Accepted
time: 286ms
memory: 72876kb

input:

971419570

output:

................................................#......................................#...#.......................................................#...................#.......#...#...
................................................#......................................#...#...........................

result:

ok res = 971419570

Test #58:

score: 0
Accepted
time: 321ms
memory: 73092kb

input:

215988289

output:

................................................................#.............#...........................#...........................#.....................#..............#......
................................................................#.............#...........................#.................

result:

ok res = 215988289

Test #59:

score: 0
Accepted
time: 309ms
memory: 72988kb

input:

233354450

output:

.................................#.......#...#........................................#................#..............#.............#...........
.................................#.......#...#........................................#................#..............#.............#...........

result:

ok res = 233354450

Test #60:

score: 0
Accepted
time: 332ms
memory: 72832kb

input:

460230232

output:

..........................................................#.....................#.....#...#.....................................#.................................#..........#......#......#..
..........................................................#.....................#.....#...#.....................

result:

ok res = 460230232

Test #61:

score: 0
Accepted
time: 336ms
memory: 73456kb

input:

169672436

output:

...........................................#.........#......#....................#....................#.................#............#......#..
...........................................#.........#......#....................#....................#.................#............#......#..

result:

ok res = 169672436

Test #62:

score: 0
Accepted
time: 357ms
memory: 72900kb

input:

116851312

output:

.......#.......#....#....#......................................#.........................#.............#...........#........
.......#.......#....#....#......................................#.........................#.............#...........#........

result:

ok res = 116851312

Test #63:

score: 0
Accepted
time: 309ms
memory: 73748kb

input:

654952096

output:

.......................................................................#......#.................#...........#.........#.........#.........#..
.......................................................................#......#.................#...........#.........#.........#.........#..

result:

ok res = 654952096

Test #64:

score: 0
Accepted
time: 302ms
memory: 72924kb

input:

456784940

output:

.......................................................#............................#........#..........................#.....................#.....................#................#........#..
.......................................................#............................#........#...............

result:

ok res = 456784940

Test #65:

score: 0
Accepted
time: 309ms
memory: 72964kb

input:

903918017

output:

......................................................................................#.....#..#..............................#.......................#......................#.........#.....#..
......................................................................................#.....#..#..............

result:

ok res = 903918017

Test #66:

score: 0
Accepted
time: 328ms
memory: 73028kb

input:

242185681

output:

.................................................#..................................#......#.......................................#....................#...............#...........#.......#..
.................................................#..................................#......#...................

result:

ok res = 242185681

Test #67:

score: 0
Accepted
time: 322ms
memory: 73124kb

input:

931841631

output:

........................................................#........................................#.........................#...................#................#..............#............
........................................................#........................................#................

result:

ok res = 931841631

Test #68:

score: 0
Accepted
time: 327ms
memory: 73576kb

input:

705201940

output:

...........................................................#.................................#................................................#...................#...........#.......#....#..
...........................................................#.................................#..................

result:

ok res = 705201940

Test #69:

score: 0
Accepted
time: 332ms
memory: 72916kb

input:

388071742

output:

.....................................#...............................................#.........................#............#.......#..
.....................................#...............................................#.........................#............#.......#..

result:

ok res = 388071742

Test #70:

score: 0
Accepted
time: 321ms
memory: 72892kb

input:

675160794

output:

................................................................................#......#...#.................................#........................#...................#..............#....
................................................................................#......#...#....................

result:

ok res = 675160794

Test #71:

score: 0
Accepted
time: 308ms
memory: 72912kb

input:

12451783

output:

............................................................#.........................#..#.....................................................#..............#.........#.......#.......#..
............................................................#.........................#..#.........................

result:

ok res = 12451783

Test #72:

score: 0
Accepted
time: 391ms
memory: 73528kb

input:

275972627

output:

...........................................#..............................#..........#......#............................................#......................#..........#........#........#..
...........................................#..............................#..........#......#.................

result:

ok res = 275972627

Test #73:

score: 0
Accepted
time: 327ms
memory: 73228kb

input:

89200061

output:

..................................................#.....................#...#..#.......................................#..........................#.............#..........#....#..
..................................................#.....................#...#..#.......................................#...

result:

ok res = 89200061

Test #74:

score: 0
Accepted
time: 304ms
memory: 73000kb

input:

873057364

output:

......................................#......................#..........................................#.......................................#.......#.....#..
......................................#......................#..........................................#....................................

result:

ok res = 873057364

Test #75:

score: 0
Accepted
time: 324ms
memory: 73008kb

input:

469614007

output:

.................................................................................#.....................................#......................#.............#...#..#..
.................................................................................#.....................................#................

result:

ok res = 469614007

Test #76:

score: 0
Accepted
time: 308ms
memory: 73032kb

input:

223340210

output:

..............................................................#.................................#......................................#......................................#.........#.....
..............................................................#.................................#...............

result:

ok res = 223340210

Test #77:

score: 0
Accepted
time: 319ms
memory: 73384kb

input:

822198166

output:

............................................................................#.....#.....#..#........................#........................#........#......#......#..
............................................................................#.....#.....#..#........................#..................

result:

ok res = 822198166

Test #78:

score: 0
Accepted
time: 290ms
memory: 72936kb

input:

455915168

output:

.............................................................#...#........................#........................#............#...........#.....#..
.............................................................#...#........................#........................#............#...........#.....#..

result:

ok res = 455915168

Test #79:

score: 0
Accepted
time: 293ms
memory: 73020kb

input:

194086925

output:

..........................................#...#...................................#............................#...........#...........#..........
..........................................#...#...................................#............................#...........#...........#..........

result:

ok res = 194086925

Test #80:

score: 0
Accepted
time: 295ms
memory: 72964kb

input:

360828081

output:

............................................................#............................#...#.......................................#.................#.........#.........#........#..
............................................................#............................#...#.........................

result:

ok res = 360828081

Test #81:

score: 0
Accepted
time: 318ms
memory: 73160kb

input:

474052493

output:

..................................................#.........................#...#.....................................#..................#................#...............#...#..
..................................................#.........................#...#.....................................#......

result:

ok res = 474052493