oj.uz

Submission #682225

# Submission time Handle Problem Language Result Execution time Memory
682225 2023-01-16T04:46:53 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 4952 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;
    for(ll i=1; i<=n; i++) cin>>x[i]>>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;
    }
    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:59:12: warning: unused variable 'mn' [-Wunused-variable]
   59 |         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 6956 KB Output is correct
2 Correct 61 ms 6952 KB Output is correct
3 Correct 40 ms 5068 KB Output is correct
4 Correct 38 ms 5128 KB Output is correct
5 Correct 54 ms 5812 KB Output is correct
6 Correct 26 ms 4556 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1503 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4525 ms 521720 KB Output is correct
2 Correct 4566 ms 518924 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 3211 ms 342716 KB Output is correct
5 Correct 4135 ms 518908 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4525 ms 521720 KB Output is correct
2 Correct 4566 ms 518924 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 3211 ms 342716 KB Output is correct
5 Correct 4135 ms 518908 KB Output is correct
6 Correct 4952 ms 518928 KB Output is correct
7 Correct 4737 ms 518864 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4718 ms 518796 KB Output is correct
11 Correct 3406 ms 342716 KB Output is correct
12 Correct 4313 ms 518848 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6956 KB Output is correct
2 Correct 61 ms 6952 KB Output is correct
3 Correct 40 ms 5068 KB Output is correct
4 Correct 38 ms 5128 KB Output is correct
5 Correct 54 ms 5812 KB Output is correct
6 Correct 26 ms 4556 KB Output is correct
7 Runtime error 1741 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 6956 KB Output is correct
2 Correct 61 ms 6952 KB Output is correct
3 Correct 40 ms 5068 KB Output is correct
4 Correct 38 ms 5128 KB Output is correct
5 Correct 54 ms 5812 KB Output is correct
6 Correct 26 ms 4556 KB Output is correct
7 Runtime error 1503 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -