oj.uz

Submission #839794

# Submission time Handle Problem Language Result Execution time Memory
839794 2023-08-30T15:51:40 Z model_code Soccer Stadium (IOI23_soccer) C++17
18 / 100
 4500 ms 12680 KB 
// partially_correct/sol_db_medium_heuristic.cpp

#include "soccer.h"
#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cassert>
#define xx first
#define yy second

using namespace std;
typedef pair<int, int> pii;

const int NUM_TRIES = 50;
const int SAMPLE_SIZE = 10;
const int maxN = 2003;
int minr[maxN], maxl[maxN];

vector<int> calc_error(int N, const vector<vector<int>> &C)
{
    auto prow = C, pcol = C;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            prow[i][j] += (j ? prow[i][j - 1] : 0);
            pcol[i][j] += (i ? pcol[i - 1][j] : 0);
        }
    }
    vector<pii> pos;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (!C[i][j])
                pos.push_back({i, j});
        }
    }
    vector<int> cnt(pos.size(), 0);
    for (int i = 0; i < pos.size(); ++i)
    {
        for (int j = 0; j < SAMPLE_SIZE; ++j)
        {
            auto p = pos[i], q = pos[rand() % pos.size()];
            if (p.xx != q.xx && p.yy != q.yy)
            {
                if (C[p.xx][q.yy] && C[q.xx][p.yy])
                {
                    cnt[i]++;
                }
                continue;
            }
            if (p > q)
                swap(p, q);
            if (p.xx == q.xx && prow[p.xx][q.yy] - (p.yy ? prow[p.xx][p.yy - 1] : 0) > 0)
            {
                cnt[i]++;
            }
            if (p.yy == q.yy && pcol[q.xx][p.yy] - (p.xx ? pcol[p.xx - 1][p.yy] : 0) > 0)
            {
                cnt[i]++;
            }
        }
    }
    return cnt;
}

bool is_regular(int N, vector<vector<int>> &C)
{
    vector<pii> ivals;
    fill(minr, minr + N + 3, maxN);
    fill(maxl, maxl + N + 3, 0);
    int cnt = 0, sum = 0;
    for (int i = 0; i < N; ++i)
    {
        int l = N, r = -1;
        for (int j = 0; j < N; ++j)
        {
            if (C[i][j] == 0)
            {
                l = min(l, j);
                r = max(r, j);
                cnt++;
            }
        }
        l++, r++;
        if (r)
            sum += r - l + 1;
        minr[l] = min(minr[l], r);
        maxl[r] = max(maxl[r], l);
        ivals.push_back({l, r});
    }
    if (sum != cnt)
    {
        return false;
    }
    for (int i = N; i >= 1; --i)
    {
        maxl[i] = max(maxl[i + 1], maxl[i]);
    }
    for (int i = 1; i <= N; ++i)
    {
        minr[i] = min(minr[i - 1], minr[i]);
    }
    for (int i = 1; i < N - 1; ++i)
    {
        pii p = ivals[i - 1];
        pii q = ivals[i];
        pii r = ivals[i + 1];
        if (q.yy - q.xx < p.yy - p.xx && q.yy - q.xx < r.yy - r.xx)
        {
            return false;
        }
    }
    for (auto q : ivals)
    {
        if (q.yy == 0)
        {
            continue;
        }
        int L = q.xx, R = q.yy;
        if (maxl[R + 1] > L || minr[L - 1] < R)
        {
            return false;
        }
    }
    return true;
}

vector<pii> make_regular(int N, const vector<vector<int>> &C, vector<pii> pos)
{
    auto wnext = [](int n, int w)
    {
        int ans = n;
        for (int i = 0; i < w; ++i)
        {
            ans = min(ans, rand() % n);
        }
        return ans;
    };
    while (true)
    {
        auto D = C;
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                D[i][j] = 1;
            }
        }
        for (pii p : pos)
        {
            D[p.xx][p.yy] = 0;
        }
        auto cnt = calc_error(N, D);
        vector<int> ind;
        for (int i = 0; i < cnt.size(); ++i)
            ind.push_back(i);
        sort(ind.begin(), ind.end(), [&](int i, int j)
             { return cnt[i] > cnt[j]; });
        if (cnt[ind[0]] == 0 && is_regular(N, D))
        {
            return pos;
        }
        int n = 0;
        for (; n < pos.size(); ++n)
        {
            if (cnt[ind[n]] == 0)
            {
                break;
            }
        }
        if (n == 0)
        {
            continue;
        }
        pos.erase(pos.begin() + ind[wnext(n, 5)]);
    }
}

int biggest_stadium(int N, vector<vector<int>> C)
{
    vector<pii> pos;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (!C[i][j])
                pos.push_back({i, j});
        }
    }
    int ans = 0;
    for (int i = 0; i < NUM_TRIES; ++i)
    {
        auto res = make_regular(N, C, pos);
        ans = max(ans, (int)res.size());
    }
    return ans;
}

Compilation message

soccer.cpp: In function 'std::vector<int> calc_error(int, const std::vector<std::vector<int> >&)':
soccer.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < pos.size(); ++i)
      |                     ~~^~~~~~~~~~~~
soccer.cpp: In function 'std::vector<std::pair<int, int> > make_regular(int, const std::vector<std::vector<int> >&, std::vector<std::pair<int, int> >)':
soccer.cpp:158:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         for (int i = 0; i < cnt.size(); ++i)
      |                         ~~^~~~~~~~~~~~
soccer.cpp:167:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |         for (; n < pos.size(); ++n)
      |                ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 1 ms 212 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 1 ms 212 KB ok
7 Execution timed out 4599 ms 1016 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 1 ms 212 KB ok
5 Correct 1 ms 212 KB ok
6 Correct 1 ms 240 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 1 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 1 ms 212 KB ok
12 Correct 1 ms 212 KB ok
13 Correct 1 ms 212 KB ok
14 Correct 1 ms 212 KB ok
15 Correct 9 ms 212 KB ok
16 Partially correct 12 ms 212 KB partial
17 Correct 13 ms 304 KB ok
18 Correct 10 ms 300 KB ok
19 Correct 4 ms 212 KB ok
20 Correct 1 ms 280 KB ok
21 Correct 1 ms 212 KB ok
22 Correct 1 ms 212 KB ok
23 Correct 1 ms 212 KB ok
24 Correct 1 ms 212 KB ok
25 Correct 1 ms 212 KB ok
26 Correct 14 ms 304 KB ok

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 1 ms 212 KB ok
5 Correct 1 ms 212 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 1 ms 240 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 1 ms 212 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 1 ms 212 KB ok
14 Correct 1 ms 212 KB ok
15 Correct 1 ms 212 KB ok
16 Correct 1 ms 212 KB ok
17 Correct 9 ms 212 KB ok
18 Partially correct 12 ms 212 KB partial
19 Correct 13 ms 304 KB ok
20 Correct 10 ms 300 KB ok
21 Correct 4 ms 212 KB ok
22 Correct 1 ms 280 KB ok
23 Correct 1 ms 212 KB ok
24 Correct 1 ms 212 KB ok
25 Correct 1 ms 212 KB ok
26 Correct 1 ms 212 KB ok
27 Correct 1 ms 212 KB ok
28 Correct 14 ms 304 KB ok
29 Correct 2 ms 288 KB ok
30 Partially correct 3802 ms 368 KB partial
31 Partially correct 3432 ms 368 KB partial
32 Partially correct 1466 ms 348 KB partial
33 Partially correct 71 ms 212 KB partial
34 Correct 3 ms 212 KB ok
35 Correct 4 ms 212 KB ok
36 Correct 13 ms 212 KB ok
37 Correct 95 ms 212 KB ok
38 Correct 44 ms 340 KB ok
39 Correct 259 ms 340 KB ok
40 Correct 1083 ms 372 KB ok
41 Partially correct 4285 ms 364 KB partial

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 1 ms 212 KB ok
5 Correct 1 ms 212 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 1 ms 240 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 1 ms 212 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 1 ms 212 KB ok
14 Correct 1 ms 212 KB ok
15 Correct 1 ms 212 KB ok
16 Correct 1 ms 212 KB ok
17 Correct 9 ms 212 KB ok
18 Partially correct 12 ms 212 KB partial
19 Correct 13 ms 304 KB ok
20 Correct 10 ms 300 KB ok
21 Correct 4 ms 212 KB ok
22 Correct 1 ms 280 KB ok
23 Correct 1 ms 212 KB ok
24 Correct 1 ms 212 KB ok
25 Correct 1 ms 212 KB ok
26 Correct 1 ms 212 KB ok
27 Correct 1 ms 212 KB ok
28 Correct 14 ms 304 KB ok
29 Correct 2 ms 288 KB ok
30 Partially correct 3802 ms 368 KB partial
31 Partially correct 3432 ms 368 KB partial
32 Partially correct 1466 ms 348 KB partial
33 Partially correct 71 ms 212 KB partial
34 Correct 3 ms 212 KB ok
35 Correct 4 ms 212 KB ok
36 Correct 13 ms 212 KB ok
37 Correct 95 ms 212 KB ok
38 Correct 44 ms 340 KB ok
39 Correct 259 ms 340 KB ok
40 Correct 1083 ms 372 KB ok
41 Partially correct 4285 ms 364 KB partial
42 Execution timed out 4513 ms 12680 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 1 ms 212 KB ok
5 Correct 1 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Execution timed out 4599 ms 1016 KB Time limit exceeded
9 Halted 0 ms 0 KB -