| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 994854 |
2024-06-08T07:39:38 Z |
김은성(#10865) |
Soccer Stadium (IOI23_soccer) |
C++17 |
|
4500 ms |
600 KB |
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F){
int mask = 0, i, ans = 0;
vector<vector<int> > temp = F;
for(i=0; i<(1<<(N*N)); i++){
int j, k;
for(j=0; j<N; j++){
for(k=0;k <N; k++){
if((N*j+k) & (1<<i)){
if(temp[j][k] == 0)
F[j][k] = 0;
else
F[j][k] = 1;
}
else
F[j][k] = 1;
}
}
ans = max(ans, stadium(N, F));
}
return ans;
}
Compilation message
soccer.cpp: In function 'bool consecutive(std::vector<int>)':
soccer.cpp:8:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | for(i=0; i+1<vec.size(); i++){
| ~~~^~~~~~~~~~~
soccer.cpp: In function 'bool bitonic(std::vector<int>)':
soccer.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(i=0; i+1<vec.size(); i++){
| ~~~^~~~~~~~~~~
soccer.cpp: In function 'std::pair<int, int> change_trend(std::vector<int>)':
soccer.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(i=0; i<vec.size(); i++){
| ~^~~~~~~~~~~
soccer.cpp: In function 'int stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:44:9: warning: unused variable 'mask' [-Wunused-variable]
44 | int mask, i, j, cnt=0, n=N;
| ^~~~
soccer.cpp:44:28: warning: unused variable 'n' [-Wunused-variable]
44 | int mask, i, j, cnt=0, n=N;
| ^
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:160:9: warning: unused variable 'mask' [-Wunused-variable]
160 | int mask = 0, i, ans = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4572 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4572 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4572 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4572 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4572 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
