oj.uz

Submission #825600

# Submission time Handle Problem Language Result Execution time Memory
825600 2023-08-15T06:00:10 Z xink Road Construction (JOI21_road_construction) C++14
11 / 100
 228 ms 10452 KB 
#include <iostream>
#include <vector>
#include <utility>
#include <sstream>
#include <climits>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <assert.h>
#define ll long long
#define ld long double
using namespace std;
const ll mod = 1e9 + 7;
typedef vector<int> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
const int maxn1 = 3e5 + 5, maxn2 = 1e6 + 6;
ii coor[maxn1];
ll dist[maxn2];

ll get_manhattan_dist(int i, int j)
{
    return abs(coor[i].first - coor[j].first) + abs(coor[i].second - coor[j].second);
}

void solve_sub1(int n, int k)
{
    int n_road = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            dist[n_road++] = get_manhattan_dist(i, j);
        }
    }
    sort(dist, dist + n_road);
    for (int i = 0; i < k; i++)
    {
        cout << dist[i] << "\n";
    }
}

void solve_sub2(int n, ll k)
{
    sort(coor, coor + n);
    ll l = 1, r = coor[n - 1].first - coor[0].first;
    while (l < r)
    {
        int m = (l + r) >> 1, l1 = 0;
        ll cnt = 0;
        for (int i = 0; i < n; i++)
        {
            while (l1 < i && get_manhattan_dist(l1, i) > m)
            {
                l1++;
            }
            cnt += i - l1;
        }
        if (cnt >= k)
        {
            r = m;
        }
        else
        {
            l = m + 1;
        }
    }
    int n_road = 0, lp = 0;
    for (int i = 0; i < n; i++)
    {
        while (lp < i && get_manhattan_dist(lp, i) >= l)
        {
            lp++;
        }
        for (int j = lp; j < i; j++)
        {
            dist[n_road++] = get_manhattan_dist(j, i);
        }
    }
    for (int i = n_road; i < k; i++)
    {
        dist[i] = l;
    }
    sort(dist, dist + k);
    for (int i = 0; i < k; i++)
    {
        cout << dist[i] << '\n';
    }
}

void solve()
{
    int n, k;
    cin >> n >> k;
    bool all_y0 = 1;
    for (int i = 0; i < n; i++)
    {
        cin >> coor[i].first >> coor[i].second;
        all_y0 &= (coor[i].second == 0);
    }
    if (n <= 1000)
    {
        solve_sub1(n, k);
        return;
    }
    if (all_y0)
    {
        solve_sub2(n, k);
        return;
    }
}

int main()
{
    // freopen("input_text", "r", stdin);
    // freopen("output_text", "w", stdout);
    // ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t-- > 0)
        solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6784 KB Output is correct
2 Correct 53 ms 6732 KB Output is correct
3 Correct 38 ms 4812 KB Output is correct
4 Correct 34 ms 4952 KB Output is correct
5 Correct 48 ms 5640 KB Output is correct
6 Correct 17 ms 4180 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 7660 KB Output is correct
2 Correct 223 ms 10312 KB Output is correct
3 Correct 35 ms 4728 KB Output is correct
4 Correct 201 ms 10188 KB Output is correct
5 Correct 154 ms 10360 KB Output is correct
6 Correct 165 ms 10452 KB Output is correct
7 Correct 157 ms 9772 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6784 KB Output is correct
2 Correct 53 ms 6732 KB Output is correct
3 Correct 38 ms 4812 KB Output is correct
4 Correct 34 ms 4952 KB Output is correct
5 Correct 48 ms 5640 KB Output is correct
6 Correct 17 ms 4180 KB Output is correct
7 Incorrect 58 ms 1792 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6784 KB Output is correct
2 Correct 53 ms 6732 KB Output is correct
3 Correct 38 ms 4812 KB Output is correct
4 Correct 34 ms 4952 KB Output is correct
5 Correct 48 ms 5640 KB Output is correct
6 Correct 17 ms 4180 KB Output is correct
7 Correct 228 ms 7660 KB Output is correct
8 Correct 223 ms 10312 KB Output is correct
9 Correct 35 ms 4728 KB Output is correct
10 Correct 201 ms 10188 KB Output is correct
11 Correct 154 ms 10360 KB Output is correct
12 Correct 165 ms 10452 KB Output is correct
13 Correct 157 ms 9772 KB Output is correct
14 Incorrect 142 ms 4984 KB Output isn't correct
15 Halted 0 ms 0 KB -