oj.uz

답안 #682263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682263 2023-01-16T05:32:18 Z vjudge1 Road Construction (JOI21_road_construction) C++17
18 / 100
 489 ms 24140 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);
}

void Baizho()
{   
	ll n, k; cin>>n>>k;
	pll a[n+11];
	for(ll i=1; i<=n; i++) cin>>a[i].ff>>a[i].ss;
	sort(a+1, a+n+1);
	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+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);
			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) {
			ll x1 = a[get.ss.ff].ff, y1 = a[get.ss.ff].ss, x2 = a[get.ss.ss+1].ff, y2 = a[get.ss.ss+1].ss;
			ll dist = getdis(x1, y1, x2, y2);
			st.insert({dist, {get.ss.ff, get.ss.ss+1}});
		}
	}
}

    
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 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 57 ms 6840 KB Output is correct
2 Correct 66 ms 6940 KB Output is correct
3 Correct 41 ms 5076 KB Output is correct
4 Correct 38 ms 5092 KB Output is correct
5 Correct 55 ms 5776 KB Output is correct
6 Correct 18 ms 4556 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 466 ms 20968 KB Output is correct
2 Correct 489 ms 24140 KB Output is correct
3 Correct 37 ms 4932 KB Output is correct
4 Correct 208 ms 24020 KB Output is correct
5 Correct 238 ms 24092 KB Output is correct
6 Correct 218 ms 24048 KB Output is correct
7 Correct 226 ms 23500 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 19868 KB Output is correct
2 Correct 219 ms 19832 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 115 ms 19864 KB Output is correct
5 Correct 115 ms 19840 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 19868 KB Output is correct
2 Correct 219 ms 19832 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 115 ms 19864 KB Output is correct
5 Correct 115 ms 19840 KB Output is correct
6 Incorrect 203 ms 19864 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 6840 KB Output is correct
2 Correct 66 ms 6940 KB Output is correct
3 Correct 41 ms 5076 KB Output is correct
4 Correct 38 ms 5092 KB Output is correct
5 Correct 55 ms 5776 KB Output is correct
6 Correct 18 ms 4556 KB Output is correct
7 Incorrect 200 ms 10576 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 6840 KB Output is correct
2 Correct 66 ms 6940 KB Output is correct
3 Correct 41 ms 5076 KB Output is correct
4 Correct 38 ms 5092 KB Output is correct
5 Correct 55 ms 5776 KB Output is correct
6 Correct 18 ms 4556 KB Output is correct
7 Correct 466 ms 20968 KB Output is correct
8 Correct 489 ms 24140 KB Output is correct
9 Correct 37 ms 4932 KB Output is correct
10 Correct 208 ms 24020 KB Output is correct
11 Correct 238 ms 24092 KB Output is correct
12 Correct 218 ms 24048 KB Output is correct
13 Correct 226 ms 23500 KB Output is correct
14 Correct 208 ms 19868 KB Output is correct
15 Correct 219 ms 19832 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 115 ms 19864 KB Output is correct
18 Correct 115 ms 19840 KB Output is correct
19 Incorrect 203 ms 19864 KB Output isn't correct
20 Halted 0 ms 0 KB -