oj.uz

Submission #682366

# Submission time Handle Problem Language Result Execution time Memory
682366 2023-01-16T07:10:38 Z vjudge1 Road Construction (JOI21_road_construction) C++17
38 / 100
 5050 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> st;
        for(ll i=1; i<=n; i++) {
            ll j = i+1;
            while(j<=n && sz(st)<k) st.insert(x[j]-x[i]), j++;
            while(j<=n && *st.rbegin()>x[j]-x[i]) {
                st.erase(prev(st.end()));
                st.insert(x[j]-x[i]), j++;
            }
        }
        for(auto to: st) 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 60 ms 7012 KB Output is correct
2 Correct 59 ms 6996 KB Output is correct
3 Correct 44 ms 5032 KB Output is correct
4 Correct 41 ms 5052 KB Output is correct
5 Correct 63 ms 5856 KB Output is correct
6 Correct 21 ms 4552 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1803 ms 17284 KB Output is correct
2 Correct 1769 ms 17252 KB Output is correct
3 Correct 97 ms 14576 KB Output is correct
4 Correct 1575 ms 17000 KB Output is correct
5 Correct 1343 ms 17120 KB Output is correct
6 Correct 1214 ms 17120 KB Output is correct
7 Correct 1325 ms 16456 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4324 ms 530748 KB Output is correct
2 Correct 5050 ms 530572 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 3070 ms 342712 KB Output is correct
5 Correct 4041 ms 518936 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4324 ms 530748 KB Output is correct
2 Correct 5050 ms 530572 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 3070 ms 342712 KB Output is correct
5 Correct 4041 ms 518936 KB Output is correct
6 Correct 4244 ms 530656 KB Output is correct
7 Correct 4488 ms 530704 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4555 ms 529212 KB Output is correct
11 Correct 3070 ms 342744 KB Output is correct
12 Correct 3932 ms 518868 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 7012 KB Output is correct
2 Correct 59 ms 6996 KB Output is correct
3 Correct 44 ms 5032 KB Output is correct
4 Correct 41 ms 5052 KB Output is correct
5 Correct 63 ms 5856 KB Output is correct
6 Correct 21 ms 4552 KB Output is correct
7 Runtime error 1474 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 60 ms 7012 KB Output is correct
2 Correct 59 ms 6996 KB Output is correct
3 Correct 44 ms 5032 KB Output is correct
4 Correct 41 ms 5052 KB Output is correct
5 Correct 63 ms 5856 KB Output is correct
6 Correct 21 ms 4552 KB Output is correct
7 Correct 1803 ms 17284 KB Output is correct
8 Correct 1769 ms 17252 KB Output is correct
9 Correct 97 ms 14576 KB Output is correct
10 Correct 1575 ms 17000 KB Output is correct
11 Correct 1343 ms 17120 KB Output is correct
12 Correct 1214 ms 17120 KB Output is correct
13 Correct 1325 ms 16456 KB Output is correct
14 Correct 4324 ms 530748 KB Output is correct
15 Correct 5050 ms 530572 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 3070 ms 342712 KB Output is correct
18 Correct 4041 ms 518936 KB Output is correct
19 Correct 4244 ms 530656 KB Output is correct
20 Correct 4488 ms 530704 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 4555 ms 529212 KB Output is correct
24 Correct 3070 ms 342744 KB Output is correct
25 Correct 3932 ms 518868 KB Output is correct
26 Runtime error 1474 ms 2097152 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -