oj.uz

답안 #682354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682354 2023-01-16T07:02:01 Z vjudge1 Road Construction (JOI21_road_construction) C++17
59 / 100
 1727 ms 22920 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], id[N], cc;
vector<pair<int, int>> v;

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

int convert(int i, int j){
    if(i < j) swap(i, j);
    return i * (n + 1) + j;
}

multiset<int> st;

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        v.pb({x[i], y[i]});
    }
    sort(all(v));
    cc = 90000000 / 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, i - cc); j < i; j++){
            if(st.size() < k){
                st.insert(dist(i, j));    
            }else{
                auto to = st.end();
                to--;
                if(*to > dist(i, j)){
                    st.erase(to);
                    st.insert(dist(i, j));
                }
            }
            
        }
    }
    while(k--){
        cout << *(st.begin()) << '\n';
        st.erase(st.begin());
    }

    //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: In function 'void solve()':
road_construction.cpp:51:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   51 |             if(st.size() < k){
      |                ~~~~~~~~~~^~~
road_construction.cpp: At global scope:
road_construction.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 14676 KB Output is correct
2 Correct 212 ms 14608 KB Output is correct
3 Correct 125 ms 14736 KB Output is correct
4 Correct 134 ms 14752 KB Output is correct
5 Correct 218 ms 13620 KB Output is correct
6 Correct 4 ms 468 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1589 ms 21168 KB Output is correct
2 Correct 1356 ms 22920 KB Output is correct
3 Correct 127 ms 14564 KB Output is correct
4 Incorrect 1076 ms 22872 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 308 ms 8248 KB Output is correct
2 Correct 319 ms 9292 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 292 ms 8164 KB Output is correct
5 Correct 310 ms 8700 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 308 ms 8248 KB Output is correct
2 Correct 319 ms 9292 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 292 ms 8164 KB Output is correct
5 Correct 310 ms 8700 KB Output is correct
6 Correct 308 ms 8252 KB Output is correct
7 Correct 317 ms 9456 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 313 ms 10104 KB Output is correct
11 Correct 295 ms 8320 KB Output is correct
12 Correct 313 ms 10172 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 14676 KB Output is correct
2 Correct 212 ms 14608 KB Output is correct
3 Correct 125 ms 14736 KB Output is correct
4 Correct 134 ms 14752 KB Output is correct
5 Correct 218 ms 13620 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 1388 ms 17132 KB Output is correct
8 Correct 1493 ms 17124 KB Output is correct
9 Correct 125 ms 14668 KB Output is correct
10 Correct 1439 ms 16492 KB Output is correct
11 Correct 1727 ms 18500 KB Output is correct
12 Correct 550 ms 19140 KB Output is correct
13 Correct 822 ms 17732 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 14676 KB Output is correct
2 Correct 212 ms 14608 KB Output is correct
3 Correct 125 ms 14736 KB Output is correct
4 Correct 134 ms 14752 KB Output is correct
5 Correct 218 ms 13620 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 1589 ms 21168 KB Output is correct
8 Correct 1356 ms 22920 KB Output is correct
9 Correct 127 ms 14564 KB Output is correct
10 Incorrect 1076 ms 22872 KB Output isn't correct
11 Halted 0 ms 0 KB -