oj.uz

Submission #682462

# Submission time Handle Problem Language Result Execution time Memory
682462 2023-01-16T09:11:08 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 7871 ms 17116 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/rope>
using namespace __gnu_cxx;

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


typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

#define precise(a) cout<<fixed<<setprecision(a)
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
// t1
const ll mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const ll N = ll(5e5)+10;
const ll K = 17;
const ll inf = 1e18;
const ld eps = 1e-15L;
//const ll B = 316;
ll lcm(ll a, ll b){ return (a / __gcd(a,b)) * b; }
//const ld P = acos(-1.0);

// ll binpow(ll a, ll b, ll m){ ll res=1;a%=m; while(b>0){ if(b&1)res=(res*a)%m; a=(a*a)%m; b/=2; } return res%m;}
ld binpow(ld a, ll b){ ld res=1; while(b>0){ if(b&1)res=(res*a); a=(a*a); b/=2; } return res;}


void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }


void precalc() {
}

ll getdis(ll x1, ll y1, ll x2, ll y2) {
    return abs(x2-x1)+abs(y2-y1);
}

ll mx[N];

bool comp(pll a, pll b) {
    ll x = a.ff, y = b.ff;
    if(abs(x) == abs(y)) {
        x = a.ss, y = b.ss;
        return abs(x)<=abs(y);
    }
    return abs(x)<=abs(y);
}

void Baizho()
{   
    ll n, k; cin>>n>>k;
    pll a[n+11];
    ll sec = 500;
    bool case2 = 1;
    for(ll i=1; i<=n; i++) {
        cin>>a[i].ff>>a[i].ss;
        if(a[i].ss!=0) case2 = 0;
    }
    sort(a+1, a+n+1);
    multiset<ll> st;
    if(n<=1000) {
        vector<ll>vec;
        for(ll i=1; i<=n-1; i++) {
            for(ll j=i+1; j<=n; j++) {
                ll x1 = a[i].ff, y1 = a[i].ss, x2 = a[j].ff, y2 = a[j].ss;
                ll dist = getdis(x1, y1, x2, y2);
                vec.pb(dist);
            }
        }
        sort(all(vec));
        for(ll i=1; i<=k; i++) {
            cout<<vec[i-1]<<"\n";
        }
        return;
    }
    for(ll i=1; i<=n-1; i++) {
        ll p = i;
        for(ll j = i+1; j<=i+sec && j<=n; j++) {
            // cout<<p<<" "<<j<<endl;
            ll x1 = a[p].ff, y1 = a[p].ss, x2 = a[j].ff, y2 = a[j].ss;
            ll dist = getdis(x1, y1, x2, y2);
            st.insert(dist);
            while(st.sz>k) {
                auto x = st.end();
                x--;
                st.erase(x);
            }
        }
    }
    for(auto x : st) cout<<x<<"\n";

    
}

    
int main() {

    // Freopen("div7");
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 

    precalc();

    int ttt = 1;
    // cin>>ttt;

    for(int i=1; i<=ttt; i++) { Baizho();}
}

Compilation message

road_construction.cpp: In function 'void Baizho()':
road_construction.cpp:92:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   92 |             while(st.sz>k) {
      |                   ~~~~~^~
road_construction.cpp:63:10: warning: variable 'case2' set but not used [-Wunused-but-set-variable]
   63 |     bool case2 = 1;
      |          ^~~~~
road_construction.cpp: In function 'void Freopen(std::string)':
road_construction.cpp:37:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:37:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6968 KB Output is correct
2 Correct 60 ms 6956 KB Output is correct
3 Correct 38 ms 5064 KB Output is correct
4 Correct 38 ms 5080 KB Output is correct
5 Correct 50 ms 5796 KB Output is correct
6 Correct 18 ms 4556 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7871 ms 17112 KB Output is correct
2 Correct 7501 ms 17116 KB Output is correct
3 Correct 32 ms 4928 KB Output is correct
4 Incorrect 7828 ms 16872 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3389 ms 4224 KB Output is correct
2 Correct 3435 ms 4224 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 3757 ms 4220 KB Output is correct
5 Correct 3395 ms 4228 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3389 ms 4224 KB Output is correct
2 Correct 3435 ms 4224 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 3757 ms 4220 KB Output is correct
5 Correct 3395 ms 4228 KB Output is correct
6 Correct 3642 ms 4224 KB Output is correct
7 Correct 3719 ms 4220 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 3749 ms 4228 KB Output is correct
11 Correct 3781 ms 4220 KB Output is correct
12 Correct 3709 ms 4224 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6968 KB Output is correct
2 Correct 60 ms 6956 KB Output is correct
3 Correct 38 ms 5064 KB Output is correct
4 Correct 38 ms 5080 KB Output is correct
5 Correct 50 ms 5796 KB Output is correct
6 Correct 18 ms 4556 KB Output is correct
7 Incorrect 3534 ms 15584 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6968 KB Output is correct
2 Correct 60 ms 6956 KB Output is correct
3 Correct 38 ms 5064 KB Output is correct
4 Correct 38 ms 5080 KB Output is correct
5 Correct 50 ms 5796 KB Output is correct
6 Correct 18 ms 4556 KB Output is correct
7 Correct 7871 ms 17112 KB Output is correct
8 Correct 7501 ms 17116 KB Output is correct
9 Correct 32 ms 4928 KB Output is correct
10 Incorrect 7828 ms 16872 KB Output isn't correct
11 Halted 0 ms 0 KB -