QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#292401#7120. SoccerGoldenglow1427Compile Error//C++146.9kb2023-12-28 03:26:402024-04-28 08:03:08

Judging History

你现在查看的是最新测评结果

  • [2024-04-28 08:03:08]
  • 管理员手动重测本题所有提交记录
查看
  • [2023-12-28 03:26:40]
  • 评测
查看
  • [2023-12-28 03:26:40]
  • 提交

answer

/*
ID: Victor Chen [mail_vi1]
PROG: Soccer Stadium
LANG: C++
*/

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cassert>

using namespace std;

const int Maxn = 2000;

typedef long long ll;

map<ll, bool> hash_mp;
map<ll, int> dp;

int n, ans;
bool mp[Maxn+10][Maxn+10];
int pre[Maxn+10][Maxn+10];

// int dp[Maxn+10][Maxn+10];

struct Rectangle
{
    int x, y; // The id signifies the rectangle.
    int l, r; // The left bound and the right bound.
    int u, d; // The upper bound and the lower bound.

    Rectangle(){}
    Rectangle(int x1, int y1, int x2, int y2)
    {
        u = x1; d = x2;
        l = y1; r = y2;
    }

    int find_area()
    {
        return (r-l+1) * (d-u+1);
    }

    ll hash()
    {
        return (((((ll)l*Maxn)+r)*Maxn)+u)*Maxn+d;
    }

    bool exist()
    {
        return l != 0;
    }

    void print()
    {
        printf("%d %d %d %d\n", u, l, d, r);
    }
}rec[Maxn+10][Maxn+10];

int cnt;
Rectangle ord[Maxn*Maxn];

bool cmp(Rectangle x, Rectangle y)
{
    if(x.d-x.u != y.d-y.u)
        return (x.d-x.u) < (y.d-y.u);
    else
        return (x.r-x.l) > (y.r-y.l);
}

Rectangle merge(Rectangle x, Rectangle y)
{
    return Rectangle(max(x.u, y.u), max(x.l, y.l), min(x.d, y.d), min(x.r, y.r));
}

int find_sum(int x1, int y1, int x2, int y2)
{
    return pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1]; 
}

Rectangle find_rect(int x, int y, int k)
{
    Rectangle ret = Rectangle();

    ret.u = x, ret.d = k;

    ret.l = ret.r = y;
    int l = 1, r = y, mid;
    while(l <= r)
    {
        mid = (l+r)/2;
        if(find_sum(x, mid, k, y) == 0)
        {
            r = mid - 1;
            ret.l = mid;
        }
        else
            l = mid + 1;
    }

    l = y, r = n;
    while(l <= r)
    {
        mid = (l+r)/2;
        if(find_sum(x, y, k, mid) == 0)
        {
            l = mid + 1;
            ret.r = mid;
        }
        else
            r = mid - 1;
    }

    return ret;
}

Rectangle find_up_rect(int x, int y, int k)
{
    Rectangle ret;

    ret.l = x, ret.r = y, ret.u = ret.d = k;

    int l = 1, r = k, mid;
    while(l <= r)
    {
        mid = (l+r)/2;
        if(find_sum(mid, x, k, y) == 0)
        {
            r = mid - 1;
            ret.u = mid;
        }
        else
            l = mid + 1;
    }

    return ret;
}
Rectangle find_down_rect(int x, int y, int k)
{
    Rectangle ret;

    ret.l = x, ret.r = y, ret.u = ret.d = k;

    int l = k, r = n, mid;
    while(l <= r)
    {
        mid = (l+r)/2;
        if(find_sum(k, x, mid, y) == 0)
        {
            l = mid + 1;
            ret.d = mid;
        }
        else
            r = mid - 1;
    }

    return ret;
}

int tp;
int nxt[Maxn+10][Maxn+10];

int biggest_stadium(int N, vector<vector<int>> F)
{
    n = N;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            mp[i][j] = F[i-1][j-1];
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + mp[i][j];
        }

    for(int i=1; i<=n; i++)
    {
        int lst0 = n+1, lst1 = n+1;
        for(int j=n; j>=1; j--)
            if(mp[i][j] == 0)
            {
                nxt[i][j] = lst1;
                lst0 = j;
            }
            else
            {
                nxt[i][j] = lst0;
                lst1 = j;
            }
    }

    // The columns.
    for(int i=1; i<=n; i++)
    {
        tp = 0;
        for(int j=1; j<=n; j++)
            if(mp[j][i] == 1)
                tp = j;
            else
            {
                rec[i][j] = find_rect(tp+1, i, j);
                rec[i][j].x = i, rec[i][j].y = j;

                if(rec[i][j].exist() && hash_mp[rec[i][j].hash()] == false)
                {
                    ord[++cnt] = rec[i][j];
                    hash_mp[rec[i][j].hash()] = true;
                }
            }
    }

    assert(n != 2000 || pre[n][n] <= 1);

    // find_rect(1, 2, 4).print();
    
    // for(int i=1; i<=n; i++)
    //     for(int j=1; j<=n; j++)
    //         rec[i][j].print();

    sort(ord+1, ord+cnt+1, cmp);
    for(int i=1; i<=cnt; i++)
    {
        dp[ord[i].hash()] = max(dp[ord[i].hash()], ord[i].find_area());
        if(ord[i].u != 1)
        {
            int r = ord[i].u-1;
            int bg, ed;
            if(mp[r][ord[i].l] == 0)
                bg = ord[i].l;
            else
                bg = nxt[r][ord[i].l];

            ed = nxt[r][bg] - 1;
                
            if(ed > ord[i].r) ed = ord[i].r;

            if(bg <= ord[i].r)
            {
                while(ed <= ord[i].r)
                {
                    Rectangle k = find_up_rect(bg, ed, ord[i].d);
                    dp[k.hash()] = max(dp[k.hash()], dp[ord[i].hash()] + k.find_area() - merge(ord[i], k).find_area());

                    if(ed == ord[i].r)
                        break;
                    
                    bg = nxt[r][ed+1];
                    ed = nxt[r][bg] - 1;

                    if(ed > ord[i].r) ed = ord[i].r;
                    if(bg > ord[i].r) break;
                }
            }
        }
        if(ord[i].d != n)
        {
            int r = ord[i].d+1;
            int bg, ed;
            if(mp[r][ord[i].l] == 0)
                bg = ord[i].l;
            else
                bg = nxt[r][ord[i].l];

            ed = nxt[r][bg] - 1;

            // assert(bg != 2 || ed != 3 || ord[i].hash() != Rectangle(1, 1, 1, 3).hash());
            
            if(ed > ord[i].r) ed = ord[i].r;

            if(bg <= ord[i].r)
            {
                while(ed <= ord[i].r)
                {
                    Rectangle k = find_down_rect(bg, ed, ord[i].u);
                    dp[k.hash()] = max(dp[k.hash()], dp[ord[i].hash()] + k.find_area() - merge(ord[i], k).find_area());

                    // assert(k.hash() != Rectangle(1, 2, 2, 3).hash() || ord[i].hash() != Rectangle(1, 1, 1, 3).hash());

                    if(ed == ord[i].r)
                        break;
                    
                    bg = nxt[r][ed+1];
                    ed = nxt[r][bg] - 1;

                    if(ed > ord[i].r) ed = ord[i].r;
                    if(bg > ord[i].r) break;
                }
            }
        }

        ans = max(ans, dp[ord[i].hash()]);
    }

    // printf("%d\n", dp[Rectangle(1, 1, 1, 3).hash()]);

    return ans;
}

int N;
vector<int> ept;
vector<vector<int>> F;

int main()
{
    freopen("read.in", "r", stdin);

    scanf("%d", &N);
    for(int i=0; i<N; i++)
    {
        F.push_back(ept);
        for(int j=0; j<N; j++)
        {
            int x;
            scanf("%d", &x);
            F[i].push_back(x);
        }
    }

    printf("%d\n", biggest_stadium(N, F));

    return 0;
}
Source code, Language: C++14

Details 

answer.code: In function ‘int main()’:
answer.code:306:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  306 |     freopen("read.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
answer.code:308:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  308 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
answer.code:315:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  315 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~
/usr/bin/ld: /tmp/cc17eO15.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccHDRmS4.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
English 繁體中文 简体中文

Server Time: 2024-12-03 21:19:00 | OpenSource Project