oj.uz

답안 #682349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682349 2023-01-16T07:00:43 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 1502 ms 21072 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 = 70000000 / 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 205 ms 14572 KB Output is correct
3 Correct 155 ms 14704 KB Output is correct
4 Correct 135 ms 14764 KB Output is correct
5 Correct 207 ms 13500 KB Output is correct
6 Correct 3 ms 468 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1300 ms 21028 KB Output is correct
2 Correct 1422 ms 21072 KB Output is correct
3 Correct 108 ms 14616 KB Output is correct
4 Incorrect 1000 ms 20924 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 8236 KB Output is correct
2 Correct 264 ms 8176 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 251 ms 8164 KB Output is correct
5 Correct 256 ms 8192 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 8236 KB Output is correct
2 Correct 264 ms 8176 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 251 ms 8164 KB Output is correct
5 Correct 256 ms 8192 KB Output is correct
6 Correct 271 ms 8400 KB Output is correct
7 Correct 258 ms 8168 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 307 ms 8224 KB Output is correct
11 Correct 243 ms 8236 KB Output is correct
12 Correct 263 ms 8156 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 14668 KB Output is correct
2 Correct 205 ms 14572 KB Output is correct
3 Correct 155 ms 14704 KB Output is correct
4 Correct 135 ms 14764 KB Output is correct
5 Correct 207 ms 13500 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1416 ms 17132 KB Output is correct
8 Correct 1434 ms 19288 KB Output is correct
9 Correct 130 ms 14876 KB Output is correct
10 Incorrect 1502 ms 18636 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 14668 KB Output is correct
2 Correct 205 ms 14572 KB Output is correct
3 Correct 155 ms 14704 KB Output is correct
4 Correct 135 ms 14764 KB Output is correct
5 Correct 207 ms 13500 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1300 ms 21028 KB Output is correct
8 Correct 1422 ms 21072 KB Output is correct
9 Correct 108 ms 14616 KB Output is correct
10 Incorrect 1000 ms 20924 KB Output isn't correct
11 Halted 0 ms 0 KB -