oj.uz

답안 #682355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682355 2023-01-16T07:02:50 Z vjudge1 Road Construction (JOI21_road_construction) C++17
59 / 100
 1951 ms 21044 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 = 100000000 / 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 213 ms 14668 KB Output is correct
2 Correct 283 ms 14592 KB Output is correct
3 Correct 121 ms 14704 KB Output is correct
4 Correct 156 ms 14720 KB Output is correct
5 Correct 192 ms 13560 KB Output is correct
6 Correct 3 ms 468 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1670 ms 21024 KB Output is correct
2 Correct 1443 ms 21044 KB Output is correct
3 Correct 118 ms 14692 KB Output is correct
4 Incorrect 1217 ms 20916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 391 ms 8248 KB Output is correct
2 Correct 379 ms 8256 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 374 ms 8180 KB Output is correct
5 Correct 566 ms 8248 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 391 ms 8248 KB Output is correct
2 Correct 379 ms 8256 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 374 ms 8180 KB Output is correct
5 Correct 566 ms 8248 KB Output is correct
6 Correct 374 ms 8380 KB Output is correct
7 Correct 363 ms 8264 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 367 ms 8256 KB Output is correct
11 Correct 392 ms 8224 KB Output is correct
12 Correct 400 ms 8236 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 14668 KB Output is correct
2 Correct 283 ms 14592 KB Output is correct
3 Correct 121 ms 14704 KB Output is correct
4 Correct 156 ms 14720 KB Output is correct
5 Correct 192 ms 13560 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1642 ms 17108 KB Output is correct
8 Correct 1510 ms 17128 KB Output is correct
9 Correct 136 ms 14712 KB Output is correct
10 Correct 1452 ms 16436 KB Output is correct
11 Correct 1951 ms 16368 KB Output is correct
12 Correct 595 ms 17132 KB Output is correct
13 Correct 902 ms 15596 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 14668 KB Output is correct
2 Correct 283 ms 14592 KB Output is correct
3 Correct 121 ms 14704 KB Output is correct
4 Correct 156 ms 14720 KB Output is correct
5 Correct 192 ms 13560 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1670 ms 21024 KB Output is correct
8 Correct 1443 ms 21044 KB Output is correct
9 Correct 118 ms 14692 KB Output is correct
10 Incorrect 1217 ms 20916 KB Output isn't correct
11 Halted 0 ms 0 KB -