oj.uz

답안 #682202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682202 2023-01-16T04:26:17 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 8211 ms 731436 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 = 10000000 / 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

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 38128 KB Output is correct
2 Correct 279 ms 38156 KB Output is correct
3 Correct 141 ms 20536 KB Output is correct
4 Correct 143 ms 20644 KB Output is correct
5 Correct 276 ms 36960 KB Output is correct
6 Correct 241 ms 35564 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7187 ms 731436 KB Output is correct
2 Correct 8211 ms 731364 KB Output is correct
3 Correct 139 ms 20392 KB Output is correct
4 Incorrect 6900 ms 731404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7770 ms 730268 KB Output is correct
2 Correct 7404 ms 730168 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 7194 ms 730168 KB Output is correct
5 Correct 7111 ms 730088 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7770 ms 730268 KB Output is correct
2 Correct 7404 ms 730168 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 7194 ms 730168 KB Output is correct
5 Correct 7111 ms 730088 KB Output is correct
6 Correct 7283 ms 730300 KB Output is correct
7 Correct 7230 ms 730300 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 7020 ms 730200 KB Output is correct
11 Correct 6382 ms 730268 KB Output is correct
12 Correct 6550 ms 730180 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 38128 KB Output is correct
2 Correct 279 ms 38156 KB Output is correct
3 Correct 141 ms 20536 KB Output is correct
4 Correct 143 ms 20644 KB Output is correct
5 Correct 276 ms 36960 KB Output is correct
6 Correct 241 ms 35564 KB Output is correct
7 Incorrect 7021 ms 716780 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 38128 KB Output is correct
2 Correct 279 ms 38156 KB Output is correct
3 Correct 141 ms 20536 KB Output is correct
4 Correct 143 ms 20644 KB Output is correct
5 Correct 276 ms 36960 KB Output is correct
6 Correct 241 ms 35564 KB Output is correct
7 Correct 7187 ms 731436 KB Output is correct
8 Correct 8211 ms 731364 KB Output is correct
9 Correct 139 ms 20392 KB Output is correct
10 Incorrect 6900 ms 731404 KB Output isn't correct
11 Halted 0 ms 0 KB -