Submission #1242342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242342		AlperenT_	Soccer Stadium (IOI23_soccer)	C++20	8 / 100	4594 ms	7608 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define int long long 
using namespace std ;
const int maxn = 30 + 10  ,s = 1000 , inf = 1e9 , mod = 998244353;
vector<vector<int32_t> > F; 
int n; 
int solve(){
    int sm =0 ;
    rep(i ,0 ,n-1)rep(j ,0  ,n-1)if(F[i][j]==0)sm++ ;
    vector <pii> vec ; 
    int sm2= 0 , L = -1 , R =0 ; 
    rep(i ,0 , n-1){
        int l = -1 , r = -1; 
        rep(j , 0 ,n-1){
            if(l ==-1 && F[i][j]==0){
                 l= j ;
                 if(L==-1) 
                L =i ;
            }
            if(F[i][j]==0){
                r = j ;
                R = i ;
            }
        }
        if(l!=-1)
        sm2 += r-l+1 ;
        vec.pb({l,r}) ;
    }
    if(sm!=sm2)return -1 ;
    int id =L ;
    rep(i ,L , R){
        if(vec[i].S-vec[i].F > vec[id].S-vec[id].F){
            id = i ;
        }
    }
    rep(i , L ,  id-1){
        int l2 = vec[i].F , r2 = vec[i].S ;
        int l = vec[i+1].F , r = vec[i+1].S ;
        if(l <= l2 && r2 <= r){
            
        }else{  
            return -1 ;
        }
    }
    per(i , R , id+1){
        int l2 = vec[i].F , r2 = vec[i].S ;
        int l = vec[i-1].F , r = vec[i-1].S ;
        if(l <= l2 && r2 <= r){
            
        }else{  
            return -1 ;
        }
    }
    vector <pair<int,pii> > vec2 ;
    rep(i ,L , R){
        vec2.pb({vec[i].S-vec[i].F , vec[i]}) ;
    }
    sort(all(vec2));
    rep(i , 0 , sz(vec2)-2){
        if(vec2[i+1].S.S >= vec2[i].S.S  && vec2[i+1].S.F <= vec2[i].S.F){

        }else{
            return -1 ;
        }
    }
    return sm ;
}
int32_t biggest_stadium(int32_t N, std::vector<std::vector<int32_t>> f){
    n = N ; 
    F = f ;
    vector <pii> vec; 
    rep(i , 0, n-1){
        rep(j , 0 ,n-1){
            if(f[i][j] == 0)vec.pb({i,j}) ;
        }
    }
    int sm =1 ;
    rep(ms , 0 , (1<<sz(vec))-1){
        int ans =0 , cnt = 0 ;
        rep(i , 0 , n-1){
            rep(j , 0 , n-1){
                if(f[i][j]== 1){
                    F[i][j] = 1; 
                }else{
                    if(ms>>cnt&1){
                        F[i][j] =1 ;
                    }else{
                        F[i][j] = 0;
                    }
                    cnt++;
                }
            }
        }
        if(solve()==-1){
            continue ;
        }
        sm = max(sm  ,sz(vec)- __builtin_popcount(ms)) ;
    }
    return sm;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30