oj.uz

Submission #682417

# Submission time Handle Problem Language Result Execution time Memory
682417 2023-01-16T08:23:13 Z vjudge1 Road Construction (JOI21_road_construction) C++17
38 / 100
 6178 ms 162116 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);
}

bool comp(pll a, pll b) {
    if(a.ff==b.ff) {
        return a.ss>=b.ss;
    }
    return a.ff<=b.ff;
}

void Baizho()
{   
    ll n, k; cin>>n>>k;
    pll a[n+11];
    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, comp);
    set<pair<ll, pll> > 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++) {
        for(ll j=i+1; j<=i+10 && 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);
            st.insert({dist, {i, j}});
        }
    }
    for(ll i=1; i<=k; i++) {
        pair<ll, pll> get = (*st.begin());
        cout<<get.ff<<"\n";
        st.erase(get);
        if(get.ss.ss!=n) {
            for(ll j = get.ss.ss+1; j<=get.ss.ss+10 && j<=n; j++) {
                ll p = get.ss.ff;
                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, {p, j}});
            }
        }
    }
    
}

    
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:58:10: warning: variable 'case2' set but not used [-Wunused-but-set-variable]
   58 |     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 58 ms 6904 KB Output is correct
2 Correct 61 ms 6844 KB Output is correct
3 Correct 38 ms 4984 KB Output is correct
4 Correct 50 ms 5112 KB Output is correct
5 Correct 53 ms 5792 KB Output is correct
6 Correct 18 ms 4476 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6157 ms 162000 KB Output is correct
2 Correct 6178 ms 161928 KB Output is correct
3 Correct 36 ms 4848 KB Output is correct
4 Correct 1561 ms 161804 KB Output is correct
5 Correct 1263 ms 162116 KB Output is correct
6 Correct 1301 ms 161980 KB Output is correct
7 Correct 1425 ms 161288 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2981 ms 160776 KB Output is correct
2 Correct 3054 ms 160640 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 939 ms 160884 KB Output is correct
5 Correct 1012 ms 160760 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2981 ms 160776 KB Output is correct
2 Correct 3054 ms 160640 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 939 ms 160884 KB Output is correct
5 Correct 1012 ms 160760 KB Output is correct
6 Correct 3113 ms 160848 KB Output is correct
7 Correct 2981 ms 160860 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2996 ms 160844 KB Output is correct
11 Correct 887 ms 160816 KB Output is correct
12 Correct 1020 ms 160764 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6904 KB Output is correct
2 Correct 61 ms 6844 KB Output is correct
3 Correct 38 ms 4984 KB Output is correct
4 Correct 50 ms 5112 KB Output is correct
5 Correct 53 ms 5792 KB Output is correct
6 Correct 18 ms 4476 KB Output is correct
7 Incorrect 2948 ms 105176 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6904 KB Output is correct
2 Correct 61 ms 6844 KB Output is correct
3 Correct 38 ms 4984 KB Output is correct
4 Correct 50 ms 5112 KB Output is correct
5 Correct 53 ms 5792 KB Output is correct
6 Correct 18 ms 4476 KB Output is correct
7 Correct 6157 ms 162000 KB Output is correct
8 Correct 6178 ms 161928 KB Output is correct
9 Correct 36 ms 4848 KB Output is correct
10 Correct 1561 ms 161804 KB Output is correct
11 Correct 1263 ms 162116 KB Output is correct
12 Correct 1301 ms 161980 KB Output is correct
13 Correct 1425 ms 161288 KB Output is correct
14 Correct 2981 ms 160776 KB Output is correct
15 Correct 3054 ms 160640 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 939 ms 160884 KB Output is correct
18 Correct 1012 ms 160760 KB Output is correct
19 Correct 3113 ms 160848 KB Output is correct
20 Correct 2981 ms 160860 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 2996 ms 160844 KB Output is correct
24 Correct 887 ms 160816 KB Output is correct
25 Correct 1020 ms 160764 KB Output is correct
26 Incorrect 2948 ms 105176 KB Output isn't correct
27 Halted 0 ms 0 KB -