| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 842344 | allin27x | 축구 경기장 (IOI23_soccer) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int prx[2001][2001];
int pry[2001][2001];
int TestCase1(int n, vector<vector<int>> a){
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (!a[i][j]) continue;
int h = min(i+1, n-i);
int w = min(j+1, n-j);
return n*n-h*v;
}
}
return n*n;
}
int TestCase2(int n, vector<vector<int>> a1){
int ans = 1;
auto a = a1;
for (int cd = 0; cd<(1<<(n*n)); cd++){
a = a1;
int bad = 0;
for (int i=0; i<n; i++) for (int j=0; j<n; j++)
if (a[i][j] && !(cd&(1<<(n*i+j)))) bad = 1;
if (bad) continue;
for (int i=0; i<n; i++) for (int j=0; j<n; j++) a[i][j] = (bool) (cd & (1<<(n*i+j)));
for (int x1 = 0; x1<n; x1++) for (int y1 = 0; y1<n; y1++){
if (a[x1][y1]) continue;
for (int x2 = 0; x2<n; x2++) for (int y2 = 0; y2<n; y2++){
if (a[x2][y2]) continue;
if (x1==x2 && y1==y2) continue;
if (x1 == x2){
for (int j=min(y1,y2); j<max(y1,y2); j ++){
if (a[x1][j]) bad = 1;
}
}
if (y1 == y2){
for (int i=min(x1,x2); i<max(x1,x2); i++){
if (a[i][y1]) bad =1;
}
}
if (a[x1][y2] && a[x2][y1]) bad = 1;
if (bad) break;
}
if (bad) break;
}
if (bad) continue;
ans = max(ans, n*n - __builtin_popcount(cd));
}
return ans;
}
int Partial(int n, vector<vector<int>> al){
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
prx[i+1][j+1] = prx[i][j+1] + a[i][j];
pry[i+1][j+1] = pry[i+1][j] + a[i][j];
}
}
vector<int> minx(n, n+1), maxx(n,0), miny(n, n+1), maxy(n, 0);
int cnt = 0;
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
cnt+=!a[i][j];
if (a[i][j]) continue;
minx[i] = min(minx[i], j);
maxx[i] = max(maxx[i], j);
miny[j] = min(miny[j], i);
maxy[j] = max(maxy[j], i);
}
}
for (int i=0; i<n; i++){
if (minx[i]==n+1) continue;
if (pry[i+1][maxx[i]+1] - pry[i+1][minx[i]] > 0) return -1;
}
for (int j=0; j<n; j++){
if (miny[j] ==n+1) continue;
if (prx[maxy[j]+1][j+1] - prx[miny[j]][j+1] > 0) return -1;
}
for (int i=0; i<n; i++){
minx[i] = n+1; maxx[i] = -1; maxy[i] = -1; miny[i] = n+1;
}
for (int i=0; i<n; i++){
int st = 0;
for (int j=0; j<n; j++){
if (a[i][j]){
if (!st) minx[i] = j;
if (st && maxx[i] == -1) maxx[i] = j;
} else st = 1;
}
}
for (int i=0; i<n; i++){
for (int j=i+1; j<n; j++){
int x1 = minx[i], y1 = maxx[i], x2 = minx[j], y2 = maxx[j];
if (x1>x2) swap(x1,x2), swap(y1,y2);
if (x1==x2) continue;
if (y1<y2) return -1;
}
}
return cnt;
}
int biggest_stadium(int n, vector<vector<int>> a){
if (n<4) return TestCase2(n,a);
int ones = 0;
for(int i=0; i<n; i++) for (int j=0; j<n; j++) ones+=a[i][j];
if (ones<=1) return TestCase1(n,a);
return Partial(n,a);
}