oj.uz

Submission #682266

# Submission time Handle Problem Language Result Execution time Memory
682266 2023-01-16T05:35:13 Z vjudge1 Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 451732 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];
	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);
	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;
	}
	if(case2) {
		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}});
			}
		}
		return;
	}
	for(ll i=1; i<=n-1; i++) {
		for(ll j=i+1; j<=i+k && 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

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6844 KB Output is correct
2 Correct 63 ms 6840 KB Output is correct
3 Correct 49 ms 5060 KB Output is correct
4 Correct 50 ms 5056 KB Output is correct
5 Correct 64 ms 5772 KB Output is correct
6 Correct 18 ms 4556 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 21048 KB Output is correct
2 Correct 523 ms 21080 KB Output is correct
3 Correct 33 ms 4848 KB Output is correct
4 Correct 228 ms 20976 KB Output is correct
5 Correct 224 ms 21120 KB Output is correct
6 Correct 229 ms 21108 KB Output is correct
7 Correct 241 ms 20284 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 19836 KB Output is correct
2 Correct 264 ms 19864 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 113 ms 19828 KB Output is correct
5 Correct 119 ms 19868 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 19836 KB Output is correct
2 Correct 264 ms 19864 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 113 ms 19828 KB Output is correct
5 Correct 119 ms 19868 KB Output is correct
6 Correct 3342 ms 160756 KB Output is correct
7 Correct 3167 ms 160768 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 3144 ms 160808 KB Output is correct
11 Correct 112 ms 19840 KB Output is correct
12 Correct 1018 ms 160808 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6844 KB Output is correct
2 Correct 63 ms 6840 KB Output is correct
3 Correct 49 ms 5060 KB Output is correct
4 Correct 50 ms 5056 KB Output is correct
5 Correct 64 ms 5772 KB Output is correct
6 Correct 18 ms 4556 KB Output is correct
7 Execution timed out 10123 ms 451732 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6844 KB Output is correct
2 Correct 63 ms 6840 KB Output is correct
3 Correct 49 ms 5060 KB Output is correct
4 Correct 50 ms 5056 KB Output is correct
5 Correct 64 ms 5772 KB Output is correct
6 Correct 18 ms 4556 KB Output is correct
7 Correct 506 ms 21048 KB Output is correct
8 Correct 523 ms 21080 KB Output is correct
9 Correct 33 ms 4848 KB Output is correct
10 Correct 228 ms 20976 KB Output is correct
11 Correct 224 ms 21120 KB Output is correct
12 Correct 229 ms 21108 KB Output is correct
13 Correct 241 ms 20284 KB Output is correct
14 Correct 211 ms 19836 KB Output is correct
15 Correct 264 ms 19864 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 113 ms 19828 KB Output is correct
18 Correct 119 ms 19868 KB Output is correct
19 Correct 3342 ms 160756 KB Output is correct
20 Correct 3167 ms 160768 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 3144 ms 160808 KB Output is correct
24 Correct 112 ms 19840 KB Output is correct
25 Correct 1018 ms 160808 KB Output is correct
26 Execution timed out 10123 ms 451732 KB Time limit exceeded
27 Halted 0 ms 0 KB -