oj.uz

Submission #682289

# Submission time Handle Problem Language Result Execution time Memory
682289 2023-01-16T05:46:58 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 4014 ms 8268 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 57 ms 6968 KB Output is correct
2 Correct 58 ms 7120 KB Output is correct
3 Correct 36 ms 5032 KB Output is correct
4 Correct 36 ms 5152 KB Output is correct
5 Correct 63 ms 5788 KB Output is correct
6 Correct 20 ms 4556 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 8092 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 3831 ms 8156 KB Output is correct
2 Correct 3854 ms 8268 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 3715 ms 8208 KB Output is correct
5 Correct 3789 ms 8156 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3831 ms 8156 KB Output is correct
2 Correct 3854 ms 8268 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 3715 ms 8208 KB Output is correct
5 Correct 3789 ms 8156 KB Output is correct
6 Correct 3767 ms 8152 KB Output is correct
7 Correct 3754 ms 8176 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 3799 ms 8156 KB Output is correct
11 Correct 3910 ms 8160 KB Output is correct
12 Correct 4014 ms 8148 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 6968 KB Output is correct
2 Correct 58 ms 7120 KB Output is correct
3 Correct 36 ms 5032 KB Output is correct
4 Correct 36 ms 5152 KB Output is correct
5 Correct 63 ms 5788 KB Output is correct
6 Correct 20 ms 4556 KB Output is correct
7 Incorrect 21 ms 3412 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 6968 KB Output is correct
2 Correct 58 ms 7120 KB Output is correct
3 Correct 36 ms 5032 KB Output is correct
4 Correct 36 ms 5152 KB Output is correct
5 Correct 63 ms 5788 KB Output is correct
6 Correct 20 ms 4556 KB Output is correct
7 Incorrect 37 ms 8092 KB Output isn't correct
8 Halted 0 ms 0 KB -