Submission #845041

#TimeUsernameProblemLanguageResultExecution timeMemory
845041JoksimKaktusSoccer Stadium (IOI23_soccer)C++17
1.50 / 100
260 ms47444 KiB
#include "soccer.h" #include "bits/stdc++.h" using namespace std; std::vector<std::vector<int>> f; bool check(int i1,int j1,int i2,int j2){ if(i1 < i2){ int temp = i1; i1 = i2; i2 = temp; temp = j1; j1 = j2; j2 = temp; } bool way = true; for(int i = i1;i >= i2;i--){ if(f[i][j1] == 1){ way = false; break; } } if(way){ if(j1 >= j2){ for(int j = j1;j >= j2;j--){ if(f[i2][j] == 1){ way = false; break; } } }else{ for(int j = j1;j <= j2;j++){ if(f[i2][j] == 1){ way = false; break; } } } } if(!way){ way = true; if(j1 >= j2){ for(int j = j1;j >= j2;j--){ if(f[i1][j] == 1){ way = false; break; } } }else{ for(int j = j1;j <= j2;j++){ if(f[i1][j] == 1){ way = false; break; } } } if(way){ for(int i = i1;i >= i2;i--){ if(f[i][j2] == 1){ return false; } } }else{ return false; } } return true; } int biggest_stadium(int N, std::vector<std::vector<int>> F) { f = std::vector<std::vector<int>>(N, std::vector<int>(N, 0)); for(int i = 0;i < N;i++){ for(int j = 0;j < N;j++){ f[i][j] = F[i][j]; } } int n,s,e,w; n = N; s = 0; w = N; e = 0; int num = 0; for(int i = 0; i < N;i++){ int con = 0; for(int j = 0;j < N;j++){ if(F[i][j] == 1){ num++; if(con == 1){ con = 2; } }else{ n = min(n,i); s = i; if(con == 0){ con = 1; }else if(con == 2){ return 1; } } } } for (int j = 0; j < N; j++) { int con = 0; for (int i = 0; i < N; i++) { if (F[i][j] == 1) { if (con == 1) { con = 2; } } else { w = min(w, j); e = j; if (con == 0) { con = 1; } else if (con == 2) { return 1; } } } } for (int i = 0; i < N; i++) { if (F[i][w] == 0) { for (int i2 = 0; i2 < N; i2++) { for (int j2 = 0; j2 < N; j2++) { if (F[i2][j2] == 0) { if (!check(i, w, i2, j2)) { cout << i << " " << w << " " << i2 << " " << j2; return 1; } } } } } if (F[i][e] == 0) { for (int i2 = 0; i2 < N; i2++) { for (int j2 = 0; j2 < N; j2++) { if (F[i2][j2] == 0) { if (!check(i, e, i2, j2)) { return 1; } } } } } if (F[n][i] == 0) { for (int i2 = 0; i2 < N; i2++) { for (int j2 = 0; j2 < N; j2++) { if (F[i2][j2] == 0) { if (!check(n, i, i2, j2)) { return 1; } } } } } if (F[s][i] == 0) { for (int i2 = 0; i2 < N; i2++) { for (int j2 = 0; j2 < N; j2++) { if (F[i2][j2] == 0) { if (!check(s, i, i2, j2)) { return 1; } } } } } } /* for (int j = 0; j < N; j++) { if (F[n][j] == 0) { for (int i = 0; i < N; i++) { if (F[s][i] == 0) { bool way1 = true; bool way1m = true; bool way2 = true; bool way2m = true; for (int k = j; k <= i; k++) { if (F[n][k] == 1) { way1 = false; break; } } for (int k = j; k >= i; k--) { if (F[n][k] == 1) { way1m = false; break; } } if (way1 || (way1m && (j > i))) { for (int k = n; k <= s; k++) { if (F[k][i] == 1) { way1 = false; break; } } for (int k = n; k >= s; k--) { if (F[k][i] == 1) { way1m = false; break; } } } if (j < i) { way1m = false; } if (!way1 && !way1m) { for (int k = n; k <= s; k++) { if (F[k][j] == 1) { way2 = false; break; } } for (int k = n; k >= s; k--) { if (F[k][j] == 1) { way2m = false; break; } } if (way2 || (way2m && (j > i))) { for (int k = j; k <= i; k++) { if (F[s][k] == 1) { way2 = false; break; } } for (int k = j; k >= i; k--) { if (F[s][k] == 1) { way2m = false; break; } } if (j < i) { way2m = false; } if (!way2 && !way2m) { return 1; } } else { return 1; } } } } } } for (int j = 0; j < N; j++) { if (F[j][w] == 0) { for (int i = 0; i < N; i++) { if (F[i][e] == 0) { bool way1 = true; bool way1m = true; bool way2 = true; bool way2m = true; for (int k = j; k <= i; k++) { if (F[k][w] == 1) { way1 = false; break; } } for (int k = j; k >= i; k--) { if (F[k][w] == 1) { way1m = false; break; } } if (way1 || (way1m && (j > i))) { for (int k = w; k <= e; k++) { if (F[i][k] == 1) { way1 = false; break; } } for (int k = w; k >= e; k--) { if (F[i][k] == 1) { way1m = false; break; } } } if (j < i) { way1m = false; } if (!way1 && !way1m) { for (int k = w; k <= e; k++) { if (F[j][k] == 1) { way2 = false; break; } } for (int k = w; k >= e; k--) { if (F[j][k] == 1) { way2m = false; break; } } if (way2 || (way2m && (j > i))) { for (int k = j; k <= i; k++) { if (F[k][e] == 1) { way2 = false; break; } } for (int k = j; k >= i; k--) { if (F[k][e] == 1) { way2m = false; break; } } if (j < i) { way2m = false; } if (!way2 && !way2m) { return 1; } } else { return 1; } } } } } } for (int i = 0; i < N; i++) { if (F[n][i] == 0) { for (int j = 0; j < N; j++) { if (F[j][w] == 0) { if (!check(n, i, j, w)) { return 1; } } } for (int j = 0; j < N; j++) { if (F[j][e] == 0) { if (!check(n, i, j, e)) { return 1; } } } } if (F[s][i] == 0) { for (int j = 0; j < N; j++) { if (F[j][w] == 0) { if (!check(s, i, j, w)) { return 1; } } } for (int j = 0; j < N; j++) { if (F[j][e] == 0) { if (!check(s, i, j, e)) { return 1; } } } } } */ return N*N-num; } /* 7 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 3 1 0 0 0 0 1 0 0 0 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...