# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
283589 | 2020-08-26T02:16:18 Z | arnold518 | World of Tank (innopolis2018_final_E) | C++14 | 976 ms | 664 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 5000; const int MAXM = 1e6; int N, M1, M2, T; int A[MAXM+10], B[MAXM+10]; int S[10][MAXN+10]; int bef[10][MAXN+10]; vector<int> solve(pii s, pii e) { memset(bef, -1, sizeof(bef)); queue<pii> Q; Q.push(s); bef[s.first][s.second]=0; while(!Q.empty()) { pii now=Q.front(); Q.pop(); if(!S[now.first][now.second+1] && bef[now.first][now.second+1]==-1) { bef[now.first][now.second+1]=1; Q.push({now.first, now.second+1}); } if(!S[3-now.first][now.second] && bef[3-now.first][now.second]==-1) { bef[3-now.first][now.second]=2; Q.push({3-now.first, now.second}); } } pii p; if(e.first!=0) { if(bef[e.first][e.second]==-1) return vector<int>(1, -1); p=e; } else { if(bef[1][e.second]!=-1) p={1, e.second}; else if(bef[2][e.second]!=-1) p={2, e.second}; else return vector<int>(1, -1); } vector<int> ans; while(1) { if(p==s) break; if(bef[p.first][p.second]==1) p.second--; else p.first=3-p.first, ans.push_back(p.second); } reverse(ans.begin(), ans.end()); return ans; } int main() { scanf("%d%d%d%d", &N, &M1, &M2, &T); for(int i=1; i<=M1; i++) scanf("%d", &A[i]), S[1][A[i]]=1; for(int i=1; i<=M2; i++) scanf("%d", &B[i]), S[2][B[i]]=1; vector<int> NO; NO.push_back(-1); vector<int> V1, V2; V1=solve({1, 0}, {0, N+1}); if(V1!=NO) { printf("Yes\n"); printf("%d\n", V1.size()); for(auto it : V1) printf("%d ", it); printf("\n"); printf("0\n"); return 0; } for(int i=1; i<=M1; i++) { if(A[i]<T) continue; S[1][A[i]]=0; V1=solve({1, 0}, {1, A[i]-1}); V2=solve({1, A[i]}, {0, N+1}); if(V1!=NO && V2!=NO) { printf("Yes\n"); printf("%d\n", V1.size()+V2.size()); for(auto it : V1) printf("%d ", it); printf("\n"); for(auto it : V2) printf("%d ", it); printf("\n"); printf("1\n"); printf("%d 1\n", A[i]-1); return 0; } S[1][A[i]]=1; } for(int i=1; i<=M2; i++) { if(B[i]<T) continue; S[2][B[i]]=0; V1=solve({1, 0}, {2, B[i]-1}); V2=solve({2, B[i]}, {0, N+1}); if(V1!=NO && V2!=NO) { printf("Yes\n"); printf("%d\n", V1.size()+V2.size()); for(auto it : V1) printf("%d ", it); printf("\n"); for(auto it : V2) printf("%d ", it); printf("\n"); printf("1\n"); printf("%d 2\n", B[i]-1); return 0; } S[2][B[i]]=1; } printf("No\n"); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20 |
2 | Correct | 1 ms | 512 KB | [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000 |
3 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000 |
4 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000 |
5 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000 |
6 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000 |
7 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000 |
8 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000 |
9 | Correct | 1 ms | 512 KB | [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000 |
10 | Correct | 1 ms | 512 KB | [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000 |
11 | Correct | 1 ms | 640 KB | [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20 |
2 | Correct | 1 ms | 512 KB | [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000 |
3 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000 |
4 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000 |
5 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000 |
6 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000 |
7 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000 |
8 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000 |
9 | Correct | 1 ms | 512 KB | [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000 |
10 | Correct | 1 ms | 512 KB | [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000 |
11 | Correct | 1 ms | 640 KB | [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000 |
12 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501 |
13 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501 |
14 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501 |
15 | Correct | 67 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501 |
16 | Correct | 976 ms | 660 KB | [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501 |
17 | Correct | 340 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501 |
18 | Correct | 390 ms | 544 KB | [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501 |
19 | Correct | 435 ms | 656 KB | [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501 |
20 | Correct | 622 ms | 652 KB | [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501 |
21 | Correct | 405 ms | 648 KB | [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501 |
22 | Correct | 931 ms | 664 KB | [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501 |
23 | Correct | 894 ms | 640 KB | [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 544 KB | [No solution found] n = 20, m1 = 12, m2 = 9, t = 3 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20 |
2 | Correct | 1 ms | 512 KB | [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000 |
3 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000 |
4 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000 |
5 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000 |
6 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000 |
7 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000 |
8 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000 |
9 | Correct | 1 ms | 512 KB | [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000 |
10 | Correct | 1 ms | 512 KB | [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000 |
11 | Correct | 1 ms | 640 KB | [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000 |
12 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501 |
13 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501 |
14 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501 |
15 | Correct | 67 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501 |
16 | Correct | 976 ms | 660 KB | [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501 |
17 | Correct | 340 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501 |
18 | Correct | 390 ms | 544 KB | [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501 |
19 | Correct | 435 ms | 656 KB | [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501 |
20 | Correct | 622 ms | 652 KB | [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501 |
21 | Correct | 405 ms | 648 KB | [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501 |
22 | Correct | 931 ms | 664 KB | [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501 |
23 | Correct | 894 ms | 640 KB | [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501 |
24 | Incorrect | 9 ms | 512 KB | [No solution found] n = 500, m1 = 197, m2 = 53, t = 2 |
25 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20 |
2 | Correct | 1 ms | 512 KB | [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000 |
3 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000 |
4 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000 |
5 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000 |
6 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000 |
7 | Correct | 2 ms | 512 KB | [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000 |
8 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000 |
9 | Correct | 1 ms | 512 KB | [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000 |
10 | Correct | 1 ms | 512 KB | [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000 |
11 | Correct | 1 ms | 640 KB | [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000 |
12 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501 |
13 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501 |
14 | Correct | 2 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501 |
15 | Correct | 67 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501 |
16 | Correct | 976 ms | 660 KB | [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501 |
17 | Correct | 340 ms | 640 KB | [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501 |
18 | Correct | 390 ms | 544 KB | [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501 |
19 | Correct | 435 ms | 656 KB | [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501 |
20 | Correct | 622 ms | 652 KB | [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501 |
21 | Correct | 405 ms | 648 KB | [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501 |
22 | Correct | 931 ms | 664 KB | [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501 |
23 | Correct | 894 ms | 640 KB | [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501 |
24 | Incorrect | 3 ms | 544 KB | [No solution found] n = 20, m1 = 12, m2 = 9, t = 3 |
25 | Halted | 0 ms | 0 KB | - |