oj.uz

답안 #682421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682421 2023-01-16T08:27:00 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 318076 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+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}});
        }
    }
    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+20 && 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

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 6900 KB Output is correct
2 Correct 61 ms 6888 KB Output is correct
3 Correct 39 ms 5052 KB Output is correct
4 Correct 37 ms 5056 KB Output is correct
5 Correct 51 ms 5784 KB Output is correct
6 Correct 19 ms 4556 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6878 ms 317324 KB Output is correct
2 Correct 6782 ms 317288 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1748 ms 317396 KB Output is correct
5 Correct 2098 ms 317356 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6878 ms 317324 KB Output is correct
2 Correct 6782 ms 317288 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1748 ms 317396 KB Output is correct
5 Correct 2098 ms 317356 KB Output is correct
6 Correct 6768 ms 317348 KB Output is correct
7 Correct 6724 ms 317556 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 7035 ms 317388 KB Output is correct
11 Correct 1722 ms 317348 KB Output is correct
12 Correct 2106 ms 317368 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 6900 KB Output is correct
2 Correct 61 ms 6888 KB Output is correct
3 Correct 39 ms 5052 KB Output is correct
4 Correct 37 ms 5056 KB Output is correct
5 Correct 51 ms 5784 KB Output is correct
6 Correct 19 ms 4556 KB Output is correct
7 Incorrect 6726 ms 210692 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 6900 KB Output is correct
2 Correct 61 ms 6888 KB Output is correct
3 Correct 39 ms 5052 KB Output is correct
4 Correct 37 ms 5056 KB Output is correct
5 Correct 51 ms 5784 KB Output is correct
6 Correct 19 ms 4556 KB Output is correct
7 Execution timed out 10116 ms 318076 KB Time limit exceeded
8 Halted 0 ms 0 KB -