oj.uz

Submission #682261

# Submission time Handle Problem Language Result Execution time Memory
682261 2023-01-16T05:30:52 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 1178256 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+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 71 ms 6932 KB Output is correct
2 Correct 60 ms 6904 KB Output is correct
3 Correct 38 ms 4976 KB Output is correct
4 Correct 38 ms 5004 KB Output is correct
5 Correct 59 ms 5788 KB Output is correct
6 Correct 17 ms 4556 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10155 ms 1178256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 19760 KB Output is correct
2 Correct 224 ms 20220 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 115 ms 20188 KB Output is correct
5 Correct 115 ms 20272 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 19760 KB Output is correct
2 Correct 224 ms 20220 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 115 ms 20188 KB Output is correct
5 Correct 115 ms 20272 KB Output is correct
6 Correct 3099 ms 161564 KB Output is correct
7 Correct 3082 ms 161652 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 3134 ms 165876 KB Output is correct
11 Correct 908 ms 163740 KB Output is correct
12 Correct 1039 ms 166000 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 6932 KB Output is correct
2 Correct 60 ms 6904 KB Output is correct
3 Correct 38 ms 4976 KB Output is correct
4 Correct 38 ms 5004 KB Output is correct
5 Correct 59 ms 5788 KB Output is correct
6 Correct 17 ms 4556 KB Output is correct
7 Execution timed out 10033 ms 479836 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 6932 KB Output is correct
2 Correct 60 ms 6904 KB Output is correct
3 Correct 38 ms 4976 KB Output is correct
4 Correct 38 ms 5004 KB Output is correct
5 Correct 59 ms 5788 KB Output is correct
6 Correct 17 ms 4556 KB Output is correct
7 Execution timed out 10155 ms 1178256 KB Time limit exceeded
8 Halted 0 ms 0 KB -