제출 #1211424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211424		user736482	축구 경기장 (IOI23_soccer)	C++20	컴파일 에러	0 ms	0 KiB

soccer

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll toint(pair<pair<ll,ll>,pair<ll,ll>>a){
    return ((a.ff.ff*2007LL+a.ff.ss)*2007LL+a.ss.ff)*2007LL+a.ss.ss;
}
pair<pair<ll,ll>,pair<ll,ll>>fromint(ll x){
    return {{(x/(2007LL*2007LL*2007LL))%2007,(x/(2007LL*2007LL))%2007},{(x/2007)%2007,x%2007}};
}
ll inv(ll aa,ll n){
    auto a=fromint(aa);
    swap(a.ss.ff,a.ss.ss);
    a.ss.ff=n-a.ss.ff+1;
    a.ss.ss=n-a.ss.ss+1;
    return toint(a);
}
pair<unordered_map<ll,vector<ll>>,vector<ll>>pomf(int n,vector<vector<int>>f){
    unordered_map<ll,vector<ll>>mp;
    vector<ll>v;
    int mx[n+7][n+7];
    int  nxt2[n+7][n+7];
    for(ll i=1;i<=n;i++){mx[0][i]=0;nxt2[n+1][i]=n+1;}
    for(ll i=1;i<=n;i++){
        mx[i][0]=10000;
        mx[i][n+1]=10000;
        for(ll j=1;j<=n;j++){
            mx[i][j]=mx[i-1][j];
            if(f[i-1][j-1])mx[i][j]=i;
        }
        mx[n+1][i]=n+1;
    }
    for(ll i=0;i<=n+1;i++)nxt2[n+1][i]=n+1;
    for(ll i=n;i>=1;i--){
        nxt2[i][n+1]=n+1;
        for(ll j=n;j>=1;j--){
            nxt2[i][j]=nxt2[i+1][j];
            if(f[i-1][j-1])nxt2[i][j]=i;
        }
        
    }
    for(ll i=1;i<=n;i++){
        ll lw[n+7],pw[n+7],lwp[n+7],pwp[n+7],pomlw[n+7];
        lwp[0]=0;
        pwp[n+1]=n+1;
        ll nxt[n+7][11];
        for(ll j=0;j<=n+1;j++)nxt[j][0]=nxt2[i][j];
        for(ll j=1;j<11;j++){
            for(ll k=0;k+(1<<j)-1<=n+1;k++)nxt[k][j]=min(nxt[k][j-1],nxt[k+(1<<(j-1))][j-1]);
        }
        for(ll j=1;j<=n;j++){
            lwp[j]=lwp[j-1];
            if(mx[i+1][j]==i+1)lwp[j]=j;
        }
        for(ll j=n;j>=1;j--){
            pwp[j]=pwp[j+1];
            if(mx[i+1][j]==i+1)pwp[j]=j;
        }
        stack<pair<ll,ll>>st;
        st.push({10000,0});
        for(ll j=1;j<=n;j++){
            while(mx[i][j]>st.top().ff)st.pop();
            pomlw[j]=st.top().ss;
            st.push({mx[i][j],j});
        }
        while(st.size())st.pop();
        st.push({10000,0});
        for(ll j=1;j<=n;j++){
            while(mx[i][j]>=st.top().ff)st.pop();
            lw[j]=st.top().ss;
            st.push({mx[i][j],j});
        }
        while(st.size())st.pop();
        st.push({10000,n+1});
        for(ll j=n;j>=1;j--){
            while(mx[i][j]>=st.top().ff)st.pop();
            pw[j]=st.top().ss;
            st.push({mx[i][j],j});
        }
        lw[0]=0;
        lw[n+1]=n+1;
        pw[0]=0;
        pw[n+1]=n+1;
        for(ll j=1;j<=n;j++){
            if(mx[i][pomlw[j]]==mx[i][j])continue;
            ll lx=lw[j]+1;
            ll px=pw[j]-1;
            ll ly=mx[i][j]+1;
            ll py=i;
            if((lwp[j]>=lx || pwp[j]<=px) && lx<=px & ly<=py){
                v.pb(toint({{lx,px},{ly,py}}));
            }
            if(lx==1 && px==n)continue;
            ll lg=log2(px-lx+1);
            ll py2=min(nxt[lx][lg],nxt[px-(1<<lg)+1][lg])-1;
            ll ly2=min(mx[i][lx-1],mx[i][px+1])+1;
            ll lx2,px2;
            if(ly2==mx[i][lx-1]+1){
                lx2=lw[lx-1]+1;
                px2=pw[lx-1]-1;
            }
            else{
                lx2=lw[px+1]+1;
                px2=pw[px+1]-1;
            }
            mp[toint({{lx2,px2},{ly2,py}})].pb(toint({{lx,px},{ly,py2}}));
        }
    }
    return {mp,v};
}
int biggest_stadium(int n,vector<vector<int>>f){
    ll ans=0;
    auto pom=pomf(n,f);
    vector<ll>states=pom.ss;
    unordered_map<ll,vector<ll>>przej=pom.ff;
    unordered_map<ll,ll>bst;
    for(ll i=0;i<n/2;i++){
        for(ll j=0;j<n;j++)swap(f[i][j],f[n-i-1][j]);
    }
    auto pom2=pomf(n,f);
    for(ll i : pom2.ss)states.pb(inv(i,n));
    for(auto it : pom2.ff){
        for(ll i : (it).ss)przej[inv((it).ff,n)].pb(inv(i,n));
    }
   vector<ll>pm[2007];
   for(ll a : states){
       auto poma=fromint(a);
       pm[poma.ff.ss-poma.ff.ff].pb(a);
   }
   states.clear();
   for(ll i=2006;i>=0;i--){
       for(ll j : pm[i])states.pb(j);
   }
    for(ll i : states){
        auto pomi=fromint(i);
        bst[i]=max(bst[i],(pomi.ff.ss-pomi.ff.ff+1)*(pomi.ss.ss-pomi.ss.ff+1));
        ans=max(ans,bst[i]);
        for(ll j : przej[i]){
            auto pomj=fromint(j);
            bst[j]=max(bst[j],bst[i]+(pomj.ss.ss-pomj.ss.ff-pomi.ss.ss+pomi.ss.ff)*(pomj.ff.ss-pomj.ff.ff+1));
        }
    }
    return ans;
}
int main(){
   // cout<<(ll)log2(3)<<" "<<(ll)log2(4)<<"\n";return 0;
   /*
    cout<<biggest_stadium(2, {{0,0},{0,0}})<<" ";
    cout<<biggest_stadium(2, {{0,0},{0,1}})<<" ";
    cout<<biggest_stadium(2, {{0,1},{0,0}})<<" ";
    cout<<biggest_stadium(2, {{0,1},{0,1}})<<" ";
    cout<<biggest_stadium(2, {{0,0},{1,0}})<<" ";
    cout<<biggest_stadium(2, {{0,0},{1,1}})<<" ";
    cout<<biggest_stadium(2, {{0,1},{1,0}})<<" ";
    cout<<biggest_stadium(2, {{0,1},{1,1}})<<" ";
    cout<<biggest_stadium(2, {{1,0},{0,0}})<<" ";
    cout<<biggest_stadium(2, {{1,0},{0,1}})<<" ";
    cout<<biggest_stadium(2, {{1,1},{0,0}})<<" ";
    cout<<biggest_stadium(2, {{1,1},{0,1}})<<" ";
    cout<<biggest_stadium(2, {{1,0},{1,0}})<<" ";
    cout<<biggest_stadium(2, {{1,0},{1,1}})<<" ";
    cout<<biggest_stadium(2, {{1,1},{1,0}})<<" ";
    cout<<biggest_stadium(2, {{1,1},{1,1}})<<" ";
    
    cout<<biggest_stadium(5, {{0, 0, 1, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{1, 0, 0, 0, 0},{0, 0, 0, 0, 0}});*/
    /*cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{1, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 1, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 1, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 1, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 1},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{1,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,1, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 1, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 1, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 1},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{1, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 1, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 1, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 1, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 1},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{1, 0, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 1, 0, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 1, 0, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 1, 0},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 1},{0, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{1, 0, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 1, 0, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 1, 0, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 1, 0}})<<" ";
    cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},{0,0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{0, 0, 0, 0, 1}})<<" ";*/
    ll ak=1000;
    vector<vector<int>>v;
    for(ll i=0;i<ak;i++){
        v.pb({});
        for(ll j=0;j<ak;j++)v.back().pb(0);
    }
    //v[0][0]=1;
    //v[0][1]=1;
    //v[2][0]=1;
    /*for(ll i=0;i<(1<<16);i++){
        for(ll j=0;j<16;j++)v[j/4][j%4]=(bool)(i&(1<<j));
        if(biggest_stadium(ak,v)==-1){
            for(auto j : v){
                for(ll k : j)cout<<k<<" ";
                cout<<"\n";
            }
            cout<<"\n";
        }
    }*/
    cout<<biggest_stadium(ak,v);
    
    //cout<<biggest_stadium(3,{{1,0,0},{0,0,0},{1,0,1}});
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/cc7JOpdI.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccv4n66l.o:soccer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status