# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
277511 | 2020-08-21T05:32:34 Z | 문홍윤(#5120) | Travelling Salesperson (CCO20_day2problem1) | C++17 | 622 ms | 24440 KB |
#include <bits/stdc++.h> #define eb emplace_back #define mp make_pair #define F first #define S second #define all(x) x.begin(), x.end() #define svec(x) sort(x.begin(), x.end()) #define press(x) x.erase(unique(x.begin(), x.end()), x.end()) using namespace std; typedef long long LL; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; const LL llinf=2e18; const int inf=1e9; char str[2010][2010]; int n; void solve(int st){ vector<int> r, b; r.eb(st); b.eb(st); for(int i=1; i<=n; i++){ if(i==st)continue; int ch=r.back(); if(str[ch][i]=='R'){ b.pop_back(); if(!b.size()){ if(ch==st&&r[0]!=st){ reverse(all(r)); b.eb(r.back()); i--; continue; } r.eb(i); b.eb(i); } else{ if(str[i][b.back()]=='B'){ if(ch==st&&r[0]!=st){ reverse(all(r)); if(str[r.back()][b.back()]=='R')r.eb(b.back()); else b.eb(r.back()); i--; continue; } r.eb(i); b.eb(i); } else{ r.eb(i); r.eb(b.back()); } } } else{ r.pop_back(); if(!r.size()){ if(ch==st&&b[0]!=st){ reverse(all(b)); r.eb(b.back()); i--; continue; } r.eb(i); b.eb(i); } else{ if(str[i][r.back()]=='R'){ if(ch==st&&b[0]!=st){ reverse(all(b)); if(str[r.back()][b.back()]=='R')r.eb(b.back()); else b.eb(r.back()); i--; continue; } r.eb(i); b.eb(i); } else{ b.eb(i); b.eb(r.back()); } } } } printf("%d\n", n); if(r[0]!=st&&b[0]!=st)while(1); if(r.size()){ for(int i=0; i<r.size()-1; i++)assert(str[r[i]][r[i+1]]=='R'); } if(b.size()){ for(int i=0; i<b.size()-1; i++)assert(str[b[i]][b[i+1]]=='B'); } if(r[0]==st){ b.pop_back(); reverse(all(b)); for(auto i:r)printf("%d ", i); for(auto i:b)printf("%d ", i); } else{ r.pop_back(); reverse(all(r)); for(auto i:b)printf("%d ", i); for(auto i:r)printf("%d ", i); } puts(""); } int main(){ scanf("%d", &n); for(int i=2; i<=n; i++)scanf("%s", str[i]+1); if(n==2)return !printf("2\n1 2\n2\n2 1"); if(n==3)return !printf("3\n1 2 3\n3\n2 3 1\n3\n3 1 2"); for(int i=2; i<=n; i++){ for(int j=1; j<i; j++)str[j][i]=str[i][j]; } for(int i=1; i<=n; i++)solve(i); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 1 ms | 256 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 0 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 512 KB | Output is correct |
16 | Correct | 530 ms | 24056 KB | Output is correct |
17 | Correct | 485 ms | 24188 KB | Output is correct |
18 | Correct | 1 ms | 384 KB | Output is correct |
19 | Correct | 482 ms | 23928 KB | Output is correct |
20 | Correct | 536 ms | 24056 KB | Output is correct |
21 | Correct | 1 ms | 384 KB | Output is correct |
22 | Correct | 485 ms | 23900 KB | Output is correct |
23 | Correct | 555 ms | 24056 KB | Output is correct |
24 | Correct | 2 ms | 512 KB | Output is correct |
25 | Correct | 488 ms | 23944 KB | Output is correct |
26 | Correct | 539 ms | 24188 KB | Output is correct |
27 | Correct | 32 ms | 2424 KB | Output is correct |
28 | Correct | 486 ms | 24056 KB | Output is correct |
29 | Correct | 494 ms | 24104 KB | Output is correct |
30 | Correct | 519 ms | 24096 KB | Output is correct |
31 | Correct | 489 ms | 24016 KB | Output is correct |
32 | Correct | 504 ms | 23928 KB | Output is correct |
33 | Correct | 503 ms | 24184 KB | Output is correct |
34 | Correct | 501 ms | 24128 KB | Output is correct |
35 | Correct | 497 ms | 24160 KB | Output is correct |
36 | Correct | 506 ms | 24044 KB | Output is correct |
37 | Correct | 496 ms | 23800 KB | Output is correct |
38 | Correct | 497 ms | 23908 KB | Output is correct |
39 | Correct | 524 ms | 24084 KB | Output is correct |
40 | Correct | 490 ms | 24160 KB | Output is correct |
41 | Correct | 478 ms | 23928 KB | Output is correct |
42 | Correct | 534 ms | 23928 KB | Output is correct |
43 | Correct | 493 ms | 24020 KB | Output is correct |
44 | Correct | 512 ms | 24040 KB | Output is correct |
45 | Correct | 492 ms | 24036 KB | Output is correct |
46 | Correct | 481 ms | 24056 KB | Output is correct |
47 | Correct | 520 ms | 24060 KB | Output is correct |
48 | Correct | 487 ms | 23928 KB | Output is correct |
49 | Correct | 494 ms | 24232 KB | Output is correct |
50 | Correct | 508 ms | 23996 KB | Output is correct |
51 | Correct | 492 ms | 23800 KB | Output is correct |
52 | Correct | 547 ms | 24268 KB | Output is correct |
53 | Correct | 550 ms | 23964 KB | Output is correct |
54 | Correct | 495 ms | 24312 KB | Output is correct |
55 | Correct | 518 ms | 24056 KB | Output is correct |
56 | Correct | 518 ms | 24112 KB | Output is correct |
57 | Correct | 513 ms | 24152 KB | Output is correct |
58 | Correct | 515 ms | 24092 KB | Output is correct |
59 | Correct | 532 ms | 24172 KB | Output is correct |
60 | Correct | 600 ms | 24176 KB | Output is correct |
61 | Correct | 598 ms | 24124 KB | Output is correct |
62 | Correct | 591 ms | 24124 KB | Output is correct |
63 | Correct | 549 ms | 24056 KB | Output is correct |
64 | Correct | 548 ms | 24184 KB | Output is correct |
65 | Correct | 622 ms | 24112 KB | Output is correct |
66 | Correct | 522 ms | 24184 KB | Output is correct |
67 | Correct | 515 ms | 24056 KB | Output is correct |
68 | Correct | 514 ms | 24056 KB | Output is correct |
69 | Correct | 554 ms | 24188 KB | Output is correct |
70 | Correct | 563 ms | 24056 KB | Output is correct |
71 | Correct | 555 ms | 24184 KB | Output is correct |
72 | Correct | 538 ms | 24060 KB | Output is correct |
73 | Correct | 569 ms | 24068 KB | Output is correct |
74 | Correct | 552 ms | 24056 KB | Output is correct |
75 | Correct | 557 ms | 24056 KB | Output is correct |
76 | Correct | 522 ms | 24184 KB | Output is correct |
77 | Correct | 518 ms | 24184 KB | Output is correct |
78 | Correct | 519 ms | 24180 KB | Output is correct |
79 | Correct | 529 ms | 24056 KB | Output is correct |
80 | Correct | 531 ms | 24056 KB | Output is correct |
81 | Correct | 542 ms | 24076 KB | Output is correct |
82 | Correct | 520 ms | 24056 KB | Output is correct |
83 | Correct | 565 ms | 24096 KB | Output is correct |
84 | Correct | 526 ms | 24032 KB | Output is correct |
85 | Correct | 564 ms | 24168 KB | Output is correct |
86 | Correct | 522 ms | 24440 KB | Output is correct |
87 | Correct | 33 ms | 2424 KB | Output is correct |
88 | Correct | 41 ms | 2424 KB | Output is correct |
89 | Correct | 523 ms | 24264 KB | Output is correct |
90 | Correct | 539 ms | 24092 KB | Output is correct |
91 | Correct | 33 ms | 2424 KB | Output is correct |
92 | Correct | 34 ms | 2552 KB | Output is correct |
93 | Correct | 541 ms | 24056 KB | Output is correct |
94 | Correct | 584 ms | 24056 KB | Output is correct |
95 | Correct | 33 ms | 2424 KB | Output is correct |
96 | Correct | 33 ms | 2424 KB | Output is correct |
97 | Correct | 519 ms | 24188 KB | Output is correct |
98 | Correct | 556 ms | 24184 KB | Output is correct |