oj.uz

Submission #1074674

# Submission time Handle Problem Language Result Execution time Memory
1074674 2024-08-25T12:09:22 Z anango Soccer Stadium (IOI23_soccer) C++17
36 / 100
 2282 ms 78880 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 416 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 604 KB ok
8 Correct 14 ms 5208 KB ok
9 Correct 229 ms 78880 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 1 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 1 ms 344 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 1 ms 348 KB ok

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 344 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 1 ms 344 KB ok
24 Correct 1 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 1 ms 344 KB ok
30 Partially correct 2252 ms 348 KB partial
31 Partially correct 2200 ms 444 KB partial
32 Partially correct 2119 ms 444 KB partial
33 Partially correct 2142 ms 440 KB partial
34 Correct 2154 ms 444 KB ok
35 Incorrect 2282 ms 348 KB wrong
36 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 344 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 1 ms 344 KB ok
24 Correct 1 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 1 ms 344 KB ok
30 Partially correct 2252 ms 348 KB partial
31 Partially correct 2200 ms 444 KB partial
32 Partially correct 2119 ms 444 KB partial
33 Partially correct 2142 ms 440 KB partial
34 Correct 2154 ms 444 KB ok
35 Incorrect 2282 ms 348 KB wrong
36 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 416 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 604 KB ok
9 Correct 14 ms 5208 KB ok
10 Correct 229 ms 78880 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 344 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 1 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 1 ms 344 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 1 ms 344 KB ok
35 Partially correct 2252 ms 348 KB partial
36 Partially correct 2200 ms 444 KB partial
37 Partially correct 2119 ms 444 KB partial
38 Partially correct 2142 ms 440 KB partial
39 Correct 2154 ms 444 KB ok
40 Incorrect 2282 ms 348 KB wrong
41 Halted 0 ms 0 KB -