oj.uz

Submission #682304

# Submission time Handle Problem Language Result Execution time Memory
682304 2023-01-16T06:02:54 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 4938 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 && n>1000) {
        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 6912 KB Output is correct
2 Correct 59 ms 7000 KB Output is correct
3 Correct 46 ms 5020 KB Output is correct
4 Correct 43 ms 5076 KB Output is correct
5 Correct 56 ms 5860 KB Output is correct
6 Correct 20 ms 4552 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 680 ms 16436 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 4358 ms 530596 KB Output is correct
2 Correct 4523 ms 530712 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 3128 ms 342816 KB Output is correct
5 Correct 4404 ms 519076 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4358 ms 530596 KB Output is correct
2 Correct 4523 ms 530712 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 3128 ms 342816 KB Output is correct
5 Correct 4404 ms 519076 KB Output is correct
6 Correct 4329 ms 530720 KB Output is correct
7 Correct 4622 ms 530720 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 4938 ms 529192 KB Output is correct
11 Correct 3300 ms 342716 KB Output is correct
12 Correct 4215 ms 518840 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6912 KB Output is correct
2 Correct 59 ms 7000 KB Output is correct
3 Correct 46 ms 5020 KB Output is correct
4 Correct 43 ms 5076 KB Output is correct
5 Correct 56 ms 5860 KB Output is correct
6 Correct 20 ms 4552 KB Output is correct
7 Runtime error 1568 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 6912 KB Output is correct
2 Correct 59 ms 7000 KB Output is correct
3 Correct 46 ms 5020 KB Output is correct
4 Correct 43 ms 5076 KB Output is correct
5 Correct 56 ms 5860 KB Output is correct
6 Correct 20 ms 4552 KB Output is correct
7 Incorrect 680 ms 16436 KB Output isn't correct
8 Halted 0 ms 0 KB -