oj.uz

Submission #682313

# Submission time Handle Problem Language Result Execution time Memory
682313 2023-01-16T06:15:39 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 1796 ms 2097152 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// #pragma GCC optimization("g", on)
// #pragma GCC optimization("03")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("inline")
// #pragma GCC optimize("-fgcse,-fgcse-lm")
// #pragma GCC optimize("-ftree-pre,-ftree-vrp")
// #pragma GCC optimize("-ffast-math")
// #pragma GCC optimize("-fipa-sra")
// #pragma GCC optimize("-fpeephole2")
// #pragma GCC optimize("-fsched-spec")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#define aboba ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define br break;
#define sp " "
#define en "\n"
#define pb push_back
#define sz size()
#define bg begin()
#define ed end()
#define in insert
#define ss second
#define ff first
#define rbg rbegin()
#define setp(a) cout << fixed; cout << setprecision(a);
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef double db;
typedef tree<
    long long,
    null_type,
    less_equal<long long>,
    rb_tree_tag,
    tree_order_statistics_node_update> orset;

void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
ll bp(ll x, ll y, ll z) { ll res = 1; while (y) { if (y & 1) { res = (res * x) % z; y--; } x = (x * x) % z; y >>= 1; } return res; }
// C(n, k) = ((fact[n] * bp(fact[k], mod - 2)) % mod * bp(fact[n - k], mod - 2)) % mod;
ll lcm(ll a, ll b) { return (a / __gcd(a, b)) * b; }
 
const ll N = 2.5e5 + 11;
const ll inf = 1e18 + 7;
ll tt = 1;
ll x[N], y[N];

void solve() { 
    ll n, k; cin >> n >> k;
    vector<ll> v;
    vector<pll> p;
    p.pb({-inf, -inf});
    for (int i = 1;i <= n;i++) {
    	cin >> x[i] >> y[i];
    	p.pb({x[i], y[i]});
	}
	sort(p.bg, p.ed);
	for (int i = 1;i <= n;i++) {
		for (int j = i + 1;j <= min({i + k, n, i + 40000ll});j++) {
			v.pb(abs(p[i].ff - p[j].ff) + abs(p[i].ss - p[j].ss));
		}
	}
	sort(v.bg, v.ed);
	for (int i = 0;i < k;i++) cout << v[i] << en;
}
   
int main() {    
    aboba  
    //freopen("numbers");
    //cin >> tt;
    for (int i = 1;i <= tt;i++) {
		solve();
    }
}

Compilation message

road_construction.cpp: In function 'void freopen(std::string)':
road_construction.cpp:47:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:47:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6992 KB Output is correct
2 Correct 68 ms 6992 KB Output is correct
3 Correct 37 ms 5128 KB Output is correct
4 Correct 38 ms 5180 KB Output is correct
5 Correct 59 ms 5824 KB Output is correct
6 Correct 18 ms 4560 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1796 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 17220 KB Output is correct
2 Correct 101 ms 16072 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 66 ms 15032 KB Output is correct
5 Correct 92 ms 16904 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 17220 KB Output is correct
2 Correct 101 ms 16072 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 66 ms 15032 KB Output is correct
5 Correct 92 ms 16904 KB Output is correct
6 Correct 318 ms 46128 KB Output is correct
7 Correct 327 ms 44952 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 333 ms 44068 KB Output is correct
11 Correct 144 ms 43980 KB Output is correct
12 Correct 169 ms 44112 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6992 KB Output is correct
2 Correct 68 ms 6992 KB Output is correct
3 Correct 37 ms 5128 KB Output is correct
4 Correct 38 ms 5180 KB Output is correct
5 Correct 59 ms 5824 KB Output is correct
6 Correct 18 ms 4560 KB Output is correct
7 Runtime error 1648 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6992 KB Output is correct
2 Correct 68 ms 6992 KB Output is correct
3 Correct 37 ms 5128 KB Output is correct
4 Correct 38 ms 5180 KB Output is correct
5 Correct 59 ms 5824 KB Output is correct
6 Correct 18 ms 4560 KB Output is correct
7 Runtime error 1796 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -