oj.uz

Submission #682200

# Submission time Handle Problem Language Result Execution time Memory
682200 2023-01-16T04:24:15 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 3484 ms 383516 KB 
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

#define int long long
#define ll long long
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define freopen(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

const int N = 250000 + 5;
const int M = 1e3 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e17;

int n, k, x[N], y[N], cc;
vector<int> ans;
vector<pair<int, int>> v;
map<int, bool> used;

int dist(int i, int j){
    return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        x[i] += 1e9 + 5;
        y[i] += 1e9 + 5;
        v.pb({x[i], y[i]});
    }
    sort(all(v));
    cc = 5000000 / n;
    for(int i = 1; i <= n; i++){
        x[i] = v[i - 1].F;
        y[i] = v[i - 1].S;
        for(int j = max(1ll, j - cc); j < i; j++){
            if(!used[i * (n + 1) + j]){
                used[i * (n + 1) + j] = 1;
                ans.pb(dist(i, j));
            }
        }
    }
    v.clear();
    for(int i = 1; i <= n; i++){
        v.pb({y[i], x[i]});
    }
    sort(all(v));
    for(int i = 1; i <= n; i++){
        x[i] = v[i - 1].S;
        y[i] = v[i - 1].F;
        for(int j = max(1ll, j - cc); j < i; j++){
            if(!used[i * (n + 1) + j]){
                used[i * (n + 1) + j] = 1;
                ans.pb(dist(i, j));
            }
        }
    }
    sort(all(ans));
    for(int i = 0; i < k; i++){
        cout << ans[i] << '\n';
    }
    //N * log() * const
}

main() {
    fast
    int tt = 1;
    // cin >> tt;
    while(tt--){
        solve();
    }
}

Compilation message

road_construction.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("O3")
      | 
road_construction.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization("unroll-loops")
      | 
road_construction.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      | 
road_construction.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main() {
      | ^~~~
road_construction.cpp: In function 'void solve()':
road_construction.cpp:62:32: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |         for(int j = max(1ll, j - cc); j < i; j++){
      |                              ~~^~~~
road_construction.cpp:47:32: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |         for(int j = max(1ll, j - cc); j < i; j++){
      |                              ~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 38064 KB Output is correct
2 Correct 280 ms 38152 KB Output is correct
3 Correct 143 ms 20516 KB Output is correct
4 Correct 148 ms 20628 KB Output is correct
5 Correct 283 ms 37096 KB Output is correct
6 Correct 253 ms 35552 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3415 ms 379248 KB Output is correct
2 Correct 3343 ms 382320 KB Output is correct
3 Correct 139 ms 20416 KB Output is correct
4 Incorrect 3143 ms 382396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3439 ms 378048 KB Output is correct
2 Correct 3484 ms 383180 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3096 ms 380956 KB Output is correct
5 Correct 3118 ms 383356 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3439 ms 378048 KB Output is correct
2 Correct 3484 ms 383180 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3096 ms 380956 KB Output is correct
5 Correct 3118 ms 383356 KB Output is correct
6 Correct 3412 ms 383196 KB Output is correct
7 Correct 3469 ms 383068 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 3416 ms 383096 KB Output is correct
11 Correct 3095 ms 381252 KB Output is correct
12 Correct 3221 ms 383516 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 38064 KB Output is correct
2 Correct 280 ms 38152 KB Output is correct
3 Correct 143 ms 20516 KB Output is correct
4 Correct 148 ms 20628 KB Output is correct
5 Correct 283 ms 37096 KB Output is correct
6 Correct 253 ms 35552 KB Output is correct
7 Incorrect 3247 ms 364836 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 38064 KB Output is correct
2 Correct 280 ms 38152 KB Output is correct
3 Correct 143 ms 20516 KB Output is correct
4 Correct 148 ms 20628 KB Output is correct
5 Correct 283 ms 37096 KB Output is correct
6 Correct 253 ms 35552 KB Output is correct
7 Correct 3415 ms 379248 KB Output is correct
8 Correct 3343 ms 382320 KB Output is correct
9 Correct 139 ms 20416 KB Output is correct
10 Incorrect 3143 ms 382396 KB Output isn't correct
11 Halted 0 ms 0 KB -