oj.uz

Submission #682212

# Submission time Handle Problem Language Result Execution time Memory
682212 2023-01-16T04:36:40 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 1643 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);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 58 ms 6976 KB Output is correct
2 Correct 64 ms 6988 KB Output is correct
3 Correct 38 ms 5040 KB Output is correct
4 Correct 38 ms 5156 KB Output is correct
5 Correct 52 ms 5828 KB Output is correct
6 Correct 23 ms 4560 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1643 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 98 ms 12340 KB Output is correct
2 Correct 95 ms 14840 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 66 ms 14916 KB Output is correct
5 Correct 87 ms 14868 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 12340 KB Output is correct
2 Correct 95 ms 14840 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 66 ms 14916 KB Output is correct
5 Correct 87 ms 14868 KB Output is correct
6 Correct 317 ms 44412 KB Output is correct
7 Correct 318 ms 46132 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 318 ms 46132 KB Output is correct
11 Correct 174 ms 43928 KB Output is correct
12 Correct 165 ms 46388 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6976 KB Output is correct
2 Correct 64 ms 6988 KB Output is correct
3 Correct 38 ms 5040 KB Output is correct
4 Correct 38 ms 5156 KB Output is correct
5 Correct 52 ms 5828 KB Output is correct
6 Correct 23 ms 4560 KB Output is correct
7 Runtime error 1579 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 58 ms 6976 KB Output is correct
2 Correct 64 ms 6988 KB Output is correct
3 Correct 38 ms 5040 KB Output is correct
4 Correct 38 ms 5156 KB Output is correct
5 Correct 52 ms 5828 KB Output is correct
6 Correct 23 ms 4560 KB Output is correct
7 Runtime error 1643 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -