oj.uz

Submission #839790

# Submission time Handle Problem Language Result Execution time Memory
839790 2023-08-30T15:51:32 Z model_code Soccer Stadium (IOI23_soccer) C++17
30 / 100
 4500 ms 876 KB 
// partially_correct/sol_db_small_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 = 10000;

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 < i; ++j)
        {
            auto p = pos[i], q = pos[j];
            if (p.xx != q.xx && p.yy != q.yy)
            {
                if (C[p.xx][q.yy] && C[q.xx][p.yy])
                {
                    cnt[i]++, cnt[j]++;
                }
                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]++, cnt[j]++;
            }
            if (p.yy == q.yy && pcol[q.xx][p.yy] - (p.xx ? pcol[p.xx - 1][p.yy] : 0) > 0)
            {
                cnt[i]++, cnt[j]++;
            }
        }
    }
    return cnt;
}

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)
        {
            return pos;
        }
        int n = 0;
        for (; n < pos.size(); ++n)
        {
            if (cnt[ind[n]] == 0)
            {
                break;
            }
        }
        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:38: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]
   38 |     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:93:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for (int i = 0; i < cnt.size(); ++i)
      |                         ~~^~~~~~~~~~~~
soccer.cpp:102: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]
  102 |         for (; n < pos.size(); ++n)
      |                ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 280 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 296 KB ok
2 Correct 9 ms 212 KB ok
3 Correct 88 ms 280 KB ok
4 Correct 134 ms 276 KB ok
5 Correct 2 ms 212 KB ok
6 Correct 26 ms 304 KB ok
7 Execution timed out 4538 ms 876 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 296 KB ok
2 Correct 9 ms 212 KB ok
3 Correct 17 ms 212 KB ok
4 Correct 17 ms 296 KB ok
5 Correct 12 ms 300 KB ok
6 Correct 17 ms 212 KB ok
7 Correct 12 ms 300 KB ok
8 Correct 9 ms 212 KB ok
9 Correct 10 ms 300 KB ok
10 Correct 17 ms 304 KB ok
11 Correct 12 ms 212 KB ok
12 Correct 12 ms 296 KB ok
13 Correct 9 ms 340 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 280 KB ok
2 Correct 6 ms 296 KB ok
3 Correct 9 ms 212 KB ok
4 Correct 17 ms 212 KB ok
5 Correct 17 ms 296 KB ok
6 Correct 12 ms 300 KB ok
7 Correct 17 ms 212 KB ok
8 Correct 12 ms 300 KB ok
9 Correct 9 ms 212 KB ok
10 Correct 10 ms 300 KB ok
11 Correct 17 ms 304 KB ok
12 Correct 12 ms 212 KB ok
13 Correct 12 ms 296 KB ok
14 Correct 9 ms 340 KB ok
15 Correct 550 ms 276 KB ok
16 Correct 894 ms 280 KB ok
17 Correct 975 ms 276 KB ok
18 Correct 502 ms 276 KB ok
19 Correct 226 ms 276 KB ok
20 Correct 14 ms 300 KB ok
21 Correct 14 ms 304 KB ok
22 Correct 30 ms 212 KB ok
23 Correct 22 ms 300 KB ok
24 Correct 23 ms 304 KB ok
25 Correct 30 ms 280 KB ok
26 Correct 982 ms 280 KB ok

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 280 KB ok
2 Correct 6 ms 296 KB ok
3 Correct 9 ms 212 KB ok
4 Correct 88 ms 280 KB ok
5 Correct 134 ms 276 KB ok
6 Correct 17 ms 212 KB ok
7 Correct 17 ms 296 KB ok
8 Correct 12 ms 300 KB ok
9 Correct 17 ms 212 KB ok
10 Correct 12 ms 300 KB ok
11 Correct 9 ms 212 KB ok
12 Correct 10 ms 300 KB ok
13 Correct 17 ms 304 KB ok
14 Correct 12 ms 212 KB ok
15 Correct 12 ms 296 KB ok
16 Correct 9 ms 340 KB ok
17 Correct 550 ms 276 KB ok
18 Correct 894 ms 280 KB ok
19 Correct 975 ms 276 KB ok
20 Correct 502 ms 276 KB ok
21 Correct 226 ms 276 KB ok
22 Correct 14 ms 300 KB ok
23 Correct 14 ms 304 KB ok
24 Correct 30 ms 212 KB ok
25 Correct 22 ms 300 KB ok
26 Correct 23 ms 304 KB ok
27 Correct 30 ms 280 KB ok
28 Correct 982 ms 280 KB ok
29 Correct 86 ms 280 KB ok
30 Execution timed out 4600 ms 328 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 280 KB ok
2 Correct 6 ms 296 KB ok
3 Correct 9 ms 212 KB ok
4 Correct 88 ms 280 KB ok
5 Correct 134 ms 276 KB ok
6 Correct 17 ms 212 KB ok
7 Correct 17 ms 296 KB ok
8 Correct 12 ms 300 KB ok
9 Correct 17 ms 212 KB ok
10 Correct 12 ms 300 KB ok
11 Correct 9 ms 212 KB ok
12 Correct 10 ms 300 KB ok
13 Correct 17 ms 304 KB ok
14 Correct 12 ms 212 KB ok
15 Correct 12 ms 296 KB ok
16 Correct 9 ms 340 KB ok
17 Correct 550 ms 276 KB ok
18 Correct 894 ms 280 KB ok
19 Correct 975 ms 276 KB ok
20 Correct 502 ms 276 KB ok
21 Correct 226 ms 276 KB ok
22 Correct 14 ms 300 KB ok
23 Correct 14 ms 304 KB ok
24 Correct 30 ms 212 KB ok
25 Correct 22 ms 300 KB ok
26 Correct 23 ms 304 KB ok
27 Correct 30 ms 280 KB ok
28 Correct 982 ms 280 KB ok
29 Correct 86 ms 280 KB ok
30 Execution timed out 4600 ms 328 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 280 KB ok
2 Correct 6 ms 296 KB ok
3 Correct 9 ms 212 KB ok
4 Correct 88 ms 280 KB ok
5 Correct 134 ms 276 KB ok
6 Correct 2 ms 212 KB ok
7 Correct 26 ms 304 KB ok
8 Execution timed out 4538 ms 876 KB Time limit exceeded
9 Halted 0 ms 0 KB -