oj.uz

답안 #682431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682431 2023-01-16T08:42:28 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 613568 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];
    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+20 && 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}});
        }
        mx[i] = min(n, i+20);
    }
    for(ll i=1; i<=k; i++) {
        pair<ll, pll> get = (*st.begin());
        cout<<get.ff<<"\n";
        st.erase(get);
        ll p = get.ss.ff, j = mx[p]+1;
        for(; j<=n && j<=mx[p]+20; j++) {
            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}});
        }
        mx[p] = min(n, mx[p]+20);
    }
    
}

    
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:62:10: warning: variable 'case2' set but not used [-Wunused-but-set-variable]
   62 |     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

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 6968 KB Output is correct
2 Correct 72 ms 6952 KB Output is correct
3 Correct 41 ms 5028 KB Output is correct
4 Correct 38 ms 5120 KB Output is correct
5 Correct 53 ms 5804 KB Output is correct
6 Correct 19 ms 4552 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10044 ms 613568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7345 ms 319244 KB Output is correct
2 Correct 7313 ms 319328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2167 ms 319260 KB Output is correct
5 Correct 2435 ms 319160 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7345 ms 319244 KB Output is correct
2 Correct 7313 ms 319328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2167 ms 319260 KB Output is correct
5 Correct 2435 ms 319160 KB Output is correct
6 Correct 7186 ms 319292 KB Output is correct
7 Correct 7047 ms 319196 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 7089 ms 319232 KB Output is correct
11 Correct 1723 ms 319288 KB Output is correct
12 Correct 2132 ms 319264 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 6968 KB Output is correct
2 Correct 72 ms 6952 KB Output is correct
3 Correct 41 ms 5028 KB Output is correct
4 Correct 38 ms 5120 KB Output is correct
5 Correct 53 ms 5804 KB Output is correct
6 Correct 19 ms 4552 KB Output is correct
7 Execution timed out 10078 ms 427436 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 6968 KB Output is correct
2 Correct 72 ms 6952 KB Output is correct
3 Correct 41 ms 5028 KB Output is correct
4 Correct 38 ms 5120 KB Output is correct
5 Correct 53 ms 5804 KB Output is correct
6 Correct 19 ms 4552 KB Output is correct
7 Execution timed out 10044 ms 613568 KB Time limit exceeded
8 Halted 0 ms 0 KB -