oj.uz

Submission #978408

# Submission time Handle Problem Language Result Execution time Memory
978408 2024-05-09T07:57:43 Z vjudge1 Road Construction (JOI21_road_construction) C++17
11 / 100
 609 ms 25172 KB 
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl '\n'
#define str string
#define fs first
#define ss second
#define all(a) a.begin(), a.end()

#define print(a) for(auto x : a) cout << x << ' '; cout << endl;

void __print(signed x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const str &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const array<int, 2> &x)
{
    cerr << '{';
    __print(x[0]);
    cerr << ',';
    __print(x[1]);
    cerr << '}';
}
template <typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.fs);
    cerr << ',';
    __print(x.ss);
    cerr << '}';
}
template <typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &y : x)
        cerr << (f++ ? "," : ""), __print(y);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v))
        cerr << ", ";
    _print(v...);
}

#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#ifdef ONLINE_JUDGE
#define debug(x...) 42
#endif

const int mod = 1e9 + 7;

void solve(){
    int n, k;
    cin >> n >> k;
    if(n <= 1000){
        int dist[n * (n - 1) / 2];
        array<int, 2> points[n];
        for (int i = 0; i < n; i++)
            cin >> points[i][0] >> points[i][1];
        int sum = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                dist[sum] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), sum++;
        sort(dist, dist + n * (n - 1) / 2);
        for (int i = 0; i < k; i++)
            cout << dist[i] << endl;
        return;
    }
    array<int, 2> points[n];
    for(int i = 0; i < n; i ++)
        cin >> points[i][0] >> points[i][1];
    sort(points, points + n);
    multiset<array<int, 2>> ml;
    int left[n], right[n];
    for(int i = 0; i < n; i ++)
        left[i] = i - 1, right[i] = i + 1;
    const int inf = 1e18;
    for(int i = 0; i < n; i ++){
        int mn = min((left[i] == -1 ? inf : points[i][0] - points[left[i]][0]), (right[i] == n ? inf : points[right[i]][0] - points[i][0]));
        ml.insert({mn, i});
    }
    for(int i = 0; i < k; i ++){
        array<int, 2> x = *ml.begin();
        ml.erase(ml.begin());
        cout << x[0];
        if(i < k - 1)
            cout << endl;
        if(left[x[1]] != -1 and points[x[1]][0] - points[left[x[1]]][0] == x[0]){
            int k = left[x[1]];
            array<int, 2> y = {min((left[k] == -1 ? inf : points[k][0] - points[left[k]][0]), (right[k] == n ? inf : points[right[k]][0] - points[k][0])), k};
            ml.erase(y);
            right[k]++;
            y = {min((left[k] == -1 ? inf : points[k][0] - points[left[k]][0]), (right[k] == n ? inf : points[right[k]][0] - points[k][0])), k};
            ml.insert(y);
            left[x[1]] --;
            y = {min((left[x[1]] == -1 ? inf : points[x[1]][0] - points[left[x[1]]][0]), (right[x[1]] == n ? inf : points[right[x[1]]][0] - points[x[1]][0])), x[1]};
            ml.insert(y);
        }
        else{
            int k = right[x[1]];
            array<int, 2> y = {min((left[k] == -1 ? inf : points[k][0] - points[left[k]][0]), (right[k] == n ? inf : points[right[k]][0] - points[k][0])), k};
            ml.erase(y);
            left[k]--;
            y = {min((left[k] == -1 ? inf : points[k][0] - points[left[k]][0]), (right[k] == n ? inf : points[right[k]][0] - points[k][0])), k};
            ml.insert(y);
            right[x[1]]++;
            y = {min((left[x[1]] == -1 ? inf : points[x[1]][0] - points[left[x[1]]][0]), (right[x[1]] == n ? inf : points[right[x[1]]][0] - points[x[1]][0])), x[1]};
            ml.insert(y);
        }
    }
}

signed main()
{
    fastio;
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

Compilation message

road_construction.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize("Ofast")
      | 
road_construction.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("Ofast")
      | 
road_construction.cpp:4: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    4 | #pragma optimize(Ofast)
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6740 KB Output is correct
2 Correct 51 ms 6736 KB Output is correct
3 Correct 33 ms 4952 KB Output is correct
4 Correct 32 ms 4944 KB Output is correct
5 Correct 49 ms 5644 KB Output is correct
6 Correct 16 ms 4188 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 25096 KB Output is correct
2 Correct 572 ms 25136 KB Output is correct
3 Correct 33 ms 4688 KB Output is correct
4 Correct 245 ms 24824 KB Output is correct
5 Correct 219 ms 25080 KB Output is correct
6 Correct 238 ms 25172 KB Output is correct
7 Correct 250 ms 24408 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6740 KB Output is correct
2 Correct 51 ms 6736 KB Output is correct
3 Correct 33 ms 4952 KB Output is correct
4 Correct 32 ms 4944 KB Output is correct
5 Correct 49 ms 5644 KB Output is correct
6 Correct 16 ms 4188 KB Output is correct
7 Incorrect 317 ms 13284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6740 KB Output is correct
2 Correct 51 ms 6736 KB Output is correct
3 Correct 33 ms 4952 KB Output is correct
4 Correct 32 ms 4944 KB Output is correct
5 Correct 49 ms 5644 KB Output is correct
6 Correct 16 ms 4188 KB Output is correct
7 Correct 609 ms 25096 KB Output is correct
8 Correct 572 ms 25136 KB Output is correct
9 Correct 33 ms 4688 KB Output is correct
10 Correct 245 ms 24824 KB Output is correct
11 Correct 219 ms 25080 KB Output is correct
12 Correct 238 ms 25172 KB Output is correct
13 Correct 250 ms 24408 KB Output is correct
14 Incorrect 166 ms 23888 KB Output isn't correct
15 Halted 0 ms 0 KB -