oj.uz

Submission #682287

# Submission time Handle Problem Language Result Execution time Memory
682287 2023-01-16T05:46:08 Z armashka Road Construction (JOI21_road_construction) C++17
32 / 100
 3990 ms 13184 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
using namespace __gnu_pbds;
 
template<class T> using ordered_multiset =tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update> ;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file(s) freopen(s".in", "r", stdin);freopen(s".out", "w", stdout);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define ft first
#define sd second
#define ll long long
#define pll pair<ll,ll>
const int N = 1e6 + 5;
const int M = 1e7 + 5;
const ll mod = 998244353;
const ll inf = 1e18;

ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res=binmul(res,x);x=binmul(x,x);ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }

ll n, k, x[N], y[N];
pll a[N];

const void solve() {
	cin >> n >> k;
	bool ok = 1;
	for (int i = 1; i <= n; ++ i) cin >> x[i] >> y[i], ok &= (y[i] == 0), a[i] = {x[i], y[i]};

	if (n <= 1000) {
	    vector <ll> v;
	    for (int i = 1; i < n; ++ i) {
	    	for (int j = i + 1; j <= n; ++ j) v.pb(abs(x[i] - x[j]) + abs(y[i] - y[j]));
	    }
	    sort(all(v));            
	    for (int i = 0; i < k; ++ i) cout << v[i] << "\n";
		return;
	}

	if (k <= 10) {     
		multiset<ll>st;
		sort(a + 1, a + n + 1);
		for (int i = 1; i <= n; ++ i) x[i] = a[i].ft, y[i] = a[i].sd;
		for (ll i = 1; i < n; ++ i) {
			for (int j = i + 1; j <= min(n, i + 5000); ++ j) {
				if (st.size() < k) st.insert(abs(x[i] - x[j]) + abs(y[i] - y[j]));
				else if (*st.rbegin() > abs(x[i] - x[j]) + abs(y[i] - y[j])) {
					st.erase(--st.end());
					st.insert(abs(x[i] - x[j]) + abs(y[i] - y[j]));
				}
			}	
		}            
		for (auto x : st) cout << x << "\n";
		return;
	}



}

int main() {
   	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	srand(time(NULL));

	ll tt = 1;
	//cin >> tt; 

	while (tt --) solve();

	return 0;
}

Compilation message

road_construction.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization("O3")
      | 
road_construction.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization("unroll-loops")
      | 
road_construction.cpp:7: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    7 | #pragma comment(linker, "/stack:200000000")
      | 
road_construction.cpp: In function 'const void solve()':
road_construction.cpp:59:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   59 |     if (st.size() < k) st.insert(abs(x[i] - x[j]) + abs(y[i] - y[j]));
      |         ~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6908 KB Output is correct
2 Correct 58 ms 6972 KB Output is correct
3 Correct 37 ms 5056 KB Output is correct
4 Correct 40 ms 5160 KB Output is correct
5 Correct 59 ms 5832 KB Output is correct
6 Correct 21 ms 4556 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 11136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3917 ms 13184 KB Output is correct
2 Correct 3875 ms 12128 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3846 ms 11060 KB Output is correct
5 Correct 3926 ms 13012 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3917 ms 13184 KB Output is correct
2 Correct 3875 ms 12128 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3846 ms 11060 KB Output is correct
5 Correct 3926 ms 13012 KB Output is correct
6 Correct 3887 ms 12804 KB Output is correct
7 Correct 3796 ms 11984 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 3854 ms 11136 KB Output is correct
11 Correct 3990 ms 11024 KB Output is correct
12 Correct 3954 ms 11136 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6908 KB Output is correct
2 Correct 58 ms 6972 KB Output is correct
3 Correct 37 ms 5056 KB Output is correct
4 Correct 40 ms 5160 KB Output is correct
5 Correct 59 ms 5832 KB Output is correct
6 Correct 21 ms 4556 KB Output is correct
7 Incorrect 22 ms 5368 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6908 KB Output is correct
2 Correct 58 ms 6972 KB Output is correct
3 Correct 37 ms 5056 KB Output is correct
4 Correct 40 ms 5160 KB Output is correct
5 Correct 59 ms 5832 KB Output is correct
6 Correct 21 ms 4556 KB Output is correct
7 Incorrect 43 ms 11136 KB Output isn't correct
8 Halted 0 ms 0 KB -