Submission #1074674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074674		anango	Soccer Stadium (IOI23_soccer)	C++17	36 / 100	2282 ms	78880 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;

mt19937 rng;
vector<vector<int>> pref;
vector<vector<signed>> field;

int INF = 1LL<<30;

int query(int a, int b, int c, int d) {
    if (a>c) swap(a,c);
    if (b>d) swap(b,d);
    return pref[c+1][d+1]-pref[a][d+1]-pref[c+1][b]+pref[a][b];
}

int union_length(vector<int> i1, vector<int> i2) {
    return max(i2[1],i1[1])-min(i2[0],i1[0])+1;
}

int length(vector<int> interval) {
    return interval[1]-interval[0]+1;
}

bool check(vector<int> i1, vector<int> i2) {
    //check whether the length of the union of the intervals is equal to the maximum length of the 2 
    return max(length(i1),length(i2))==union_length(i1,i2);
}
void prv(vector<int> v) {
    for (auto i:v) {
        cout << i <<" ";
    }
    cout << endl;
}

signed biggest_stadium(signed N, vector<vector<signed>> F) {
    //the stadium is valid iff for every pair of cells (a,b) and (c,d), 
    //everything in the paths (a,b) to (a,d) to (c,d) is inside
    //or everything in the paths (a,b) to (a,c) to (c,d) is inside
    n=N;
    field=F;
    pref=vector<vector<int>>(n+1,vector<int>(n+1,0));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            pref[i+1][j+1] = pref[i+1][j]+pref[i][j+1]-pref[i][j]+F[i][j];
            
        }
    }
    for (int i=0; i<=n; i++) {
        for (int j=0; j<=n; j++) {
            //cout << pref[i][j] <<" ";
        }
        //cout << endl;
    }
    if (pref[n][n]<=1) {
        if (pref[n][n]==0) return n*n;
        //subtask 1
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (F[i][j]==1) {
                    int mi = min({(i+1)*(j+1),(n-i)*(j+1),(i+1)*(n-j),(n-i)*(n-j)});
                    return n*n-mi;
                }
            }
        }
    }
    if (n>=31) {
        vector<vector<int>> rows(n,{INF,-INF});
        vector<vector<int>> cols(n,{INF,-INF});
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (F[i][j]==0) {
                    rows[i][0] = min(rows[i][0],j);
                    rows[i][1] = max(rows[i][1],j);
                    cols[j][0] = min(cols[j][0],i);
                    cols[j][1] = max(cols[j][1],i);
                }
            }
        }
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (F[i][j]==1) {
                    if (rows[i][0]<=j && j<=rows[i][1]) {
                        return 0;
                    }
                    if (cols[j][0]<=i && i<=cols[j][1]) {
                        return 0;
                    }
                }
            }
        }
        for (int i=0; i<n; i++) {
            for (int j=i+1; j<n; j++) {
                if (!check(rows[i],rows[j])) {
                    return 0;
                }
            }
        }
        for (int i=0; i<n; i++) {
            for (int j=i+1; j<n; j++) {
                if (!check(cols[i],cols[j])) {
                    return 0;
                }
            }
        }
        return n*n-pref[n][n];
    }
    //EM = current expansion mask
    int jambloat = -1;
    for (int EM=0; EM<1LL<<(n-1); EM++) {
        if (n>=20) {
            EM+=rng()%100000;
        }
        int l = 0;
        int r = n-1;
        vector<int> ep;
        for (int i=0; i<n-1; i++) {
            if (EM&(1LL<<i)) {
                ep.push_back(l);
                l++;
            }
            else {
                ep.push_back(r);
                r--;
            }
        }
        ep.push_back(l);
        reverse(ep.begin(), ep.end());
        //prv(ep);
        int dp[n+1][n+1][2]; //dp[i][j] = best given the row number and how much has already been expanded (or contracted)
        for (int i=0; i<=n; i++) {
            for (int j=0; j<=n; j++) {
                dp[i][j][0] = dp[i][j][1] = -INF;
            }
        }
        vector<pair<int,int>> bounds(n+1); //the left and right if we expand upto the ith expansion
        bounds[0] = {ep[0],ep[0]-1};
        int mi = INF;
        int ma = -1;
        for (int i=0; i<n; i++) {
            mi=min(mi,ep[i]);
            ma=max(ma,ep[i]);
            bounds[i+1] = {mi,ma};
        }
        //cout << query(3,0,3,2) << " " << pref[n][n] << " " << pref[3][5] << " " << pref[4][3]-pref[4][0]-pref[3][3]+pref[3][0] << endl;
        dp[0][0][0] = 0;
        for (int i=0; i<n; i++) {
            //previous row
            for (int expand=0; expand<2; expand++) { //0 is expanding, 1 is contracting
                for (int prevexp=0; prevexp<=n; prevexp++) {
                    //if (prevexp>0 && query(i,bounds[prevexp].first,i,bounds[prevexp].second)!=0) continue;
                    for (int newexp=0; newexp<=n; newexp++) {
                        if (newexp>prevexp && expand==1) continue;
                        if (newexp>0 && query(i,bounds[newexp].first,i,bounds[newexp].second)!=0) continue;
                        int delta = bounds[newexp].second-bounds[newexp].first+1;
                        int newexpand = 0;
                        if (expand==0) {
                            if (newexp<prevexp) {
                                newexpand=1;
                            }
                        }
                        else {
                            newexpand = 1;
                        }
                        //cout << "HERE" << " " << i <<" " << expand <<" " << prevexp <<" " << newexp <<" " << newexpand <<" " << delta << " " << bounds[newexp].first <<" " << bounds[newexp].second << " " << query(i,bounds[newexp].first,i,bounds[newexp].second) << endl;
                        dp[i+1][newexp][newexpand] = max(dp[i+1][newexp][newexpand],dp[i][prevexp][expand]+delta);
                    }
                }
            }
        }
        int ans = -1;
        for (int i=0; i<=n; i++) {
            for (int j=0; j<=n; j++) {
                for (int k=0; k<2; k++) {
                    //cout << "DOING " << i <<" " << j <<" " << k <<" " << dp[i][j][k] << endl;
                    ans=max(ans,dp[i][j][k]);
                }
            }
        }
        //prv(ep);
        jambloat=max(jambloat,ans);
        //cout << ma <<" " << ans << endl;
    }
    return jambloat;
    


}

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