oj.uz

Submission #682229

# Submission time Handle Problem Language Result Execution time Memory
682229 2023-01-16T04:53:06 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 4723 ms 2097152 KB 
#include "bits/stdc++.h"
using namespace std;

// #define ORD_SET
// #define ROPE
#ifdef ORD_SET
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    template<typename T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif
#ifdef ROPE
    #include <ext/rope>
    using namespace __gnu_cxx;
#endif        

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using ll = long long;
using ld = long double;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
// #define ll int
void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
void NotInteractive() { ios_base::sync_with_stdio(false); cin.tie(NULL); }
void pre(ll a) { cout<<fixed<<setprecision(a); }
ll bit(ll x) { return __builtin_popcountll(x); }
ll binpow(ll x, ll y, ll z) { ll pow = 1; while(y) { if(y&1) pow *= x, pow %= z; x *= x, x %= z; y >>= 1; } return pow; }
template<typename T> T gcd(T a, T b) { if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b) { return a/gcd(a, b)*b; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct sn { ll l, r, x; }; // a.swap(b)
ll B = 316;
const ll mod = (ll)1e9+7;
const ll inf = (ll)1e18+7;
const ll MX = LLONG_MAX;
const ll MN = LLONG_MIN;
const ld P = acos(-1.0);
const ll N = (ll)3e5+5;
ll x[N], y[N];

void kigash() {
    ll n, k;
    cin>>n>>k;
    set<ll> st;
    for(ll i=1; i<=n; i++) cin>>x[i]>>y[i], st.insert(y[i]);
    if(k<=10 && n>1000) {
        vector<pair<pair<ll, ll>, ll>> v;
        for(ll i=1; i<=n; i++) v.pb({{x[i], y[i]}, i});
        sort(all(v));
        vector<ll> ans;
        ll mn = MX;
        map<pair<ll, ll>, ll> used;
        for(ll i=0; i<n; i++) {
            for(ll j=i+1; j<min(i+11, n); j++) {
                ll d = abs(v[i].ff.ff-v[j].ff.ff)+abs(v[i].ff.ss-v[j].ff.ss);
                ans.pb(d);
                used[{v[j].ss, v[i].ss}] = used[{v[i].ss, v[j].ss}] = 1;
            }
        }
        v.clear();
        for(ll i=1; i<=n; i++) v.pb({{y[i], x[i]}, i});
        sort(all(v));
        for(ll i=0; i<n; i++) {
            for(ll j=i+1; j<min(i+11, n); j++) {
                if(used[{v[j].ss, v[i].ss}]) continue;
                ll d = abs(v[i].ff.ff-v[j].ff.ff)+abs(v[i].ff.ss-v[j].ff.ss);
                ans.pb(d);
            }
        }
        sort(all(ans));
        for(ll i=0; i<k; i++) cout<<ans[i]<<"\n";
        return;
    }
    if(sz(st)==1 && *st.begin()==0) {
        sort(x+1, x+1+n);
        multiset<ll> ans;
        for(ll i=1; i<=n; i++) {
            ll j = i+1;
            while(j<=n && sz(ans)<k) ans.insert(x[j]-x[i]);
            while(j<=n && x[j]-x[i]<*ans.rbegin()) ans.erase(prev(ans.end())), ans.insert(x[j]-x[i]);
        }
        for(auto to: ans) cout<<to<<"\n";
        return;
    }
    vector<ll> ans;
    for(ll i=1; i<=n; i++) {
        for(ll j=i+1; j<=n; j++) ans.pb(abs(x[i]-x[j])+abs(y[i]-y[j]));
    }
    sort(all(ans));
    for(ll i=0; i<k; i++) cout<<ans[i]<<"\n";
    return;
}

signed main(/**/) {
    // freopen("");
    NotInteractive();
    // precalc();
    
    ll tt = 1;
    // cin>>tt;
    for(ll i=1; i<=tt; i++) kigash();
    
    exit(0);
}

Compilation message

road_construction.cpp: In function 'void kigash()':
road_construction.cpp:60:12: warning: unused variable 'mn' [-Wunused-variable]
   60 |         ll mn = MX;
      |            ^~
road_construction.cpp: In function 'void freopen(std::string)':
road_construction.cpp:31:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:31:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7012 KB Output is correct
2 Correct 59 ms 7012 KB Output is correct
3 Correct 38 ms 5032 KB Output is correct
4 Correct 41 ms 5132 KB Output is correct
5 Correct 57 ms 5844 KB Output is correct
6 Correct 22 ms 4552 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 687 ms 16352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4310 ms 530560 KB Output is correct
2 Correct 4723 ms 530604 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3042 ms 342684 KB Output is correct
5 Correct 3999 ms 518916 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4310 ms 530560 KB Output is correct
2 Correct 4723 ms 530604 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3042 ms 342684 KB Output is correct
5 Correct 3999 ms 518916 KB Output is correct
6 Correct 4284 ms 530592 KB Output is correct
7 Correct 4695 ms 530700 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 4412 ms 529508 KB Output is correct
11 Correct 2992 ms 342832 KB Output is correct
12 Correct 3888 ms 518984 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7012 KB Output is correct
2 Correct 59 ms 7012 KB Output is correct
3 Correct 38 ms 5032 KB Output is correct
4 Correct 41 ms 5132 KB Output is correct
5 Correct 57 ms 5844 KB Output is correct
6 Correct 22 ms 4552 KB Output is correct
7 Runtime error 1428 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7012 KB Output is correct
2 Correct 59 ms 7012 KB Output is correct
3 Correct 38 ms 5032 KB Output is correct
4 Correct 41 ms 5132 KB Output is correct
5 Correct 57 ms 5844 KB Output is correct
6 Correct 22 ms 4552 KB Output is correct
7 Incorrect 687 ms 16352 KB Output isn't correct
8 Halted 0 ms 0 KB -