제출 #1209778

#제출 시각아이디문제언어결과실행 시간메모리
1209778PagodePaivaSoccer Stadium (IOI23_soccer)C++20
3.50 / 100
200 ms31916 KiB
#include "soccer.h" #include<bits/stdc++.h> using namespace std; const int N = 2010; int linha_l[N], linha_r[N], coluna_l[N], coluna_r[N]; int linha_total[N], coluna_total[N]; int soma_linha[N], soma_coluna[N]; int pref_linha[N], pref_coluna[N]; int intercessao(int l1, int r1, int l2, int r2){ ////cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n'; if(l1 > l2 or (l1 == l2 and r2 > r1)){ swap(l1, l2); swap(r1, r2); } if(l1 > r2 or l2 > r1) return 0; if(l1 <= l2 and r2 <= r1){ return pref_linha[r2] - (l2 > 0 ? pref_linha[l2-1] : 0); } return pref_linha[r2] - (l1 > 0 ? pref_linha[l1-1] : 0); } int intercessao2(int l1, int r1, int l2, int r2){ if(l1 > l2 or (l1 == l2 and r2 > r1)){ swap(l1, l2); swap(r1, r2); } if(l1 > r2 or l2 > r1) return 0; if(l1 <= l2 and r2 <= r1){ return pref_coluna[r2] - (l2 > 0 ? pref_coluna[l2-1] : 0); } return pref_coluna[r2] - (l1 > 0 ? pref_coluna[l1-1] : 0); } int biggest_stadium(int n, vector<vector<int>> m){ int tot = 0; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ soma_linha[i] += (1-m[i][j]); soma_coluna[j] += (1-m[i][j]); } } pref_linha[0] = soma_linha[0]; pref_coluna[0] = soma_coluna[0]; for(int i = 1;i < n;i++){ pref_linha[i] = pref_linha[i-1] + soma_linha[i]; pref_coluna[i] = pref_coluna[i-1] + soma_coluna[i]; } for(int i = 0;i < n;i++){ int aux = 0; for(int j = 0;j < n;j++){ if(m[i][j] == 0){ tot++; } if(m[i][j] == 0 and aux == 0){ aux = 1; } if(m[i][j] == 1 and aux == 1){ aux = 2; } if(m[i][j] == 0 and aux == 2){ return 0; } } } for(int j = 0;j < n;j++){ int aux = 0; for(int i = 0;i < n;i++){ if(m[i][j] == 0 and aux == 0){ aux = 1; } if(m[i][j] == 1 and aux == 1){ aux = 2; } if(m[i][j] == 0 and aux == 2){ return 0; } } } for(int i = 0;i < n;i++){ linha_l[i] = n+1, linha_r[i] = -1; for(int j = 0;j < n;j++){ if(m[i][j] == 0){ linha_l[i] = min(linha_l[i], j); linha_r[i] = max(linha_r[i], j); } } ////////cout << linha_l[i] << ' ' << linha_r[i] << '\n'; } for(int j = 0;j < n; j++){ coluna_l[j] = n+1, coluna_r[j] = -1; for(int i = 0;i < n;i++){ if(m[i][j] == 0){ coluna_l[j] = min(coluna_l[j], i); coluna_r[j] = max(coluna_r[j], i); } } ////////cout << coluna_l[j] << ' ' << coluna_r[j] << '\n'; } ////////cout << tot << '\n'; for(int i = 0;i < n;i++){ int calc = 0; for(int j = 0;j < n;j++){ if(m[i][j] == 0){ calc += coluna_r[j] - coluna_l[j]+1; } } linha_total[i] = calc; } for(int j = 0;j < n;j++){ int calc = 0; for(int i = 0;i < n;i++){ if(m[i][j] == 0){ calc += linha_r[i] - linha_l[i]+1; } } coluna_total[j] = calc; } for(int i = 0;i < n;i++){ int l1 = linha_l[i], r1 = linha_r[i]; if(l1 > r1) continue; int small_coluna = l1; for(int j = l1;j <= r1;j++){ if(coluna_l[j] < coluna_l[small_coluna]) small_coluna = j; } int big_coluna = l1; for(int j = l1;j <= r1;j++){ if(coluna_r[j] > coluna_r[small_coluna]) big_coluna = j; } l1 = small_coluna; r1 = big_coluna; ////cout << l1 << ' ' << r1 << '\n'; ////cout << coluna_total[l1] << ' ' << coluna_total[r1] << '\n'; int ans = coluna_total[l1] + coluna_total[r1]; ans -= intercessao(coluna_l[l1], coluna_r[l1], coluna_l[r1], coluna_r[r1]); ////cout << ans << '\n'; if(ans != tot){ ////cout << 1 << ' '; ////cout << i << '\n'; return 0; } } for(int j = 0;j < n;j++){ int l1 = coluna_l[j], r1 = coluna_r[j]; if(l1 > r1) continue; int small_coluna = l1; for(int i = l1;i <= r1;i++){ if(linha_l[i] < linha_l[small_coluna]) small_coluna = i; } int big_coluna = l1; for(int i = l1;i <= r1;i++){ if(linha_r[i] > linha_r[small_coluna]) big_coluna = i; } l1 = small_coluna; r1 = big_coluna; int ans = linha_total[l1] + linha_total[r1]; //////cout << linha_total[l1] << ' ' << linha_total[r1] << '\n'; ans -= intercessao2(linha_l[l1], linha_r[l1], linha_l[r1], linha_r[r1]); //////cout << ans << '\n'; if(ans != tot){ //cout << 2 << ' '; //cout << j << '\n'; return 0; } } return tot; }
#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...