| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 994875 |
2024-06-08T07:58:31 Z |
김은성(#10865) |
Soccer Stadium (IOI23_soccer) |
C++17 |
|
0 ms |
348 KB |
#define SUB
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef SUB
int l[2009], r[2009], i;
int psumr[2009][2009], psumc[2009][2009];
bool consecutive(vector<int> vec){
int i;
for(i=0; i+1<vec.size(); i++){
if(vec[i+1] != vec[i] + 1)
return false;
}
return true;
}
bool bitonic(vector<int> vec){
int i, trend = 0;
for(i=0; i+1<vec.size(); i++){
//printf("vec=%d %d trend=%d\n", vec[i], vec[i+1], trend);
if(vec[i] < vec[i+1] && trend)
return false;
if(vec[i] > vec[i+1])
trend = 1;
}
return true;
}
pair<int, int> change_trend(vector<int> vec){
int i;
vector<int> opt;
int mx = -12839423;
for(i=0; i<vec.size(); i++){
//printf("vec[i]=%d\n", vec[i]);
if(vec[i] > mx){
opt.clear();
opt.push_back(i);
mx = vec[i];
}
else if(vec[i] == mx)
opt.push_back(i);
}
return make_pair(opt[0], opt.back());
}
int stadium(int N, std::vector<std::vector<int>> F)
{
vector<int> temp;
int mask, i, j, cnt=0, n=N;
srand(time(NULL));
vector<vector<int> > orgf = F;
for(i=0; i<N; i++){
vector<int> f;
for(j=0; j<N; j++){
if(!F[i][j])
f.push_back(j), cnt++;
}
if(!f.empty()){
if(!consecutive(f))
return 0;
temp.push_back(i);
l[i] = f[0];
r[i] = f.back();
}
else{
l[i] = r[i] = -1;
}
}
if(!consecutive(temp))
return 0;
for(i=0; i<N; i++){
for(j=0; j<N; j++){
psumc[i+1][j+1] = psumc[i+1][j] + F[i][j];
psumr[i+1][j+1] = psumr[i][j+1] + F[i][j];
}
}
for(i=0; i<N; i++){
for(j=i; j<N; j++){
//printf("i=%d l=%d r=%d\n", i,l[i], r[i]);
if(l[i]==-1 || l[j] == -1)
continue;
int temp = psumr[j+1][l[i]+1] - psumr[i][l[i]+1];
if(l[i] <= r[j])
temp += psumc[j+1][r[j]+1] - psumc[j+1][l[i]];
else
temp += psumc[j+1][l[i]+1] - psumc[j+1][r[j]];
int temp2 = psumr[j+1][r[j]+1] - psumr[i][r[j]+1];
if(l[i] <= r[j])
temp2 += psumc[i+1][l[i]+1] - psumc[i+1][r[j]];
else
temp2 += psumc[i+1][r[j]+1] - psumc[i+1][l[i]];
//printf("i=%d j=%d temp=%d temp2=%d\n", i, j, temp, temp2);
if(temp && temp2)
return 0;
}
}
for(i=0; i<N; i++){
for(j=i; j<N; j++){
//printf("i=%d l=%d r=%d\n", i,l[i], r[i]);
if(l[i]==-1 || l[j] == -1)
continue;
int temp = psumr[j+1][r[i]+1] - psumr[i][r[i]+1];
if(r[i] <= l[j])
temp += psumc[j+1][l[j]+1] - psumc[j+1][r[i]];
else
temp += psumc[j+1][r[i]+1] - psumc[j+1][l[j]];
int temp2 = psumr[j+1][l[j]+1] - psumr[i][l[j]+1];
if(r[i] <= l[j])
temp2 += psumc[i+1][r[i]+1] - psumc[i+1][l[j]];
else
temp2 += psumc[i+1][l[j]+1] - psumc[i+1][r[i]];
//printf("i=%d j=%d temp=%d temp2=%d\n", i, j, temp, temp2);
if(temp && temp2)
return 0;
}
}
for(i=0; i<N; i++){
for(j=i; j<N; j++){
//printf("i=%d l=%d r=%d\n", i,l[i], r[i]);
if(l[i]==-1 || l[j] == -1)
continue;
int temp = psumr[j+1][l[i]+1] - psumr[i][l[i]+1];
if(l[i] <= l[j])
temp += psumc[j+1][l[j]+1] - psumc[j+1][l[i]];
else
temp += psumc[j+1][l[i]+1] - psumc[j+1][l[j]];
int temp2 = psumr[j+1][l[j]+1] - psumr[i][l[j]+1];
if(l[i] <= l[j])
temp2 += psumc[i+1][l[i]+1] - psumc[i+1][l[j]];
else
temp2 += psumc[i+1][l[j]+1] - psumc[i+1][l[i]];
//printf("i=%d j=%d temp=%d temp2=%d\n", i, j, temp, temp2);
if(temp && temp2)
return 0;
}
}
for(i=0; i<N; i++){
for(j=i; j<N; j++){
//printf("i=%d l=%d r=%d\n", i,l[i], r[i]);
if(l[i]==-1 || l[j] == -1)
continue;
int temp = psumr[j+1][r[i]+1] - psumr[i][r[i]+1];
if(r[i] <= r[j])
temp += psumc[j+1][r[j]+1] - psumc[j+1][r[i]];
else
temp += psumc[j+1][r[i]+1] - psumc[j+1][r[j]];
int temp2 = psumr[j+1][r[j]+1] - psumr[i][r[j]+1];
if(r[i] <= r[j])
temp2 += psumc[i+1][r[i]+1] - psumc[i+1][r[j]];
else
temp2 += psumc[i+1][r[j]+1] - psumc[i+1][r[i]];
//printf("i=%d j=%d temp=%d temp2=%d\n", i, j, temp, temp2);
if(temp && temp2)
return 0;
}
}
return cnt;
}
#endif
int biggest_stadium(int N, std::vector<std::vector<int>> F){
int mask = 0, i, j, r=-1, c=-1;
for(i=0; i<N; i++){
for(j=0; j<N; j++){
if(F[i][j]){
r=i;
c=j;
}
}
}
if(r==-1 && c==-1)
return N*N;
int b1 = r, b2 = N-1-r, a1 = c, a2 = N-1-r;
int mx = 0;
mx = max(mx, N*b1 + N*a1 - a1*b1);
mx = max(mx, N*b2 + N*a1 - a1*b2);
mx = max(mx, N*b2 + N*a2 - a2*b2);
mx = max(mx, N*b1 + N*a2 - a2*b1);
return mx;
}
Compilation message
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:163:9: warning: unused variable 'mask' [-Wunused-variable]
163 | int mask = 0, i, j, r=-1, c=-1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
344 KB |
partial |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
344 KB |
partial |
| 2 |
Correct |
0 ms |
344 KB |
ok |
| 3 |
Incorrect |
0 ms |
348 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
344 KB |
partial |
| 2 |
Correct |
0 ms |
344 KB |
ok |
| 3 |
Incorrect |
0 ms |
348 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
344 KB |
partial |
| 2 |
Correct |
0 ms |
344 KB |
ok |
| 3 |
Incorrect |
0 ms |
348 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
344 KB |
partial |
| 2 |
Correct |
0 ms |
344 KB |
ok |
| 3 |
Incorrect |
0 ms |
348 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
