# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
106360 |
2019-04-18T03:04:25 Z |
aviroop123 |
Kralj (COCI16_kralj) |
C++14 |
|
2000 ms |
12140 KB |
#include "bits/stdc++.h"
// #include "ext/pb_ds/assoc_container.hpp"
// #include "ext/pb_ds/tree_policy.hpp"
// using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
// #define int long long
#define pb push_back
#define fi first
#define se second
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define sz(x) (int)x.size()
const int mod = 1e9 + 7;
const int mod1 = 998244353;
typedef long double f80;
#ifndef LOCAL
#pragma GCC optimize ("O2")
#define endl '\n'
#endif
// template<typename T>
// using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
ll pwr(ll a,ll b, ll mod){
a %= mod;
int ans = 1;
while(b){
if(b & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
void solve(){
int n;
cin >> n;
vector<int> a(n), b(n), v(n);
fr(i, 0, n - 1){
cin >> a[i];
}
fr(i, 0, n - 1){
cin >> b[i];
}
vector<pii> lol;
fr(i, 0, n - 1){
cin >> v[i];
lol.pb({v[i], a[i] - 1});
}
sort(all(lol));
srand(time(NULL));
random_shuffle(all(lol));
vector<int> ans(n, -1);
for(pii x : lol){
int p = x.se;
int val = x.fi;
while(ans[p] != -1){
if(ans[p] > val && val > b[p]){
swap(ans[p], val);
}
else if(ans[p] < b[p] && val > b[p]){
swap(ans[p], val);
}
else if(ans[p] < b[p] && val < ans[p]){
swap(ans[p], val);
}
p++;
if(p == n) p = 0;
}
ans[p] = val;
}
int tot = 0;
fr(i, 0, n - 1){
tot += (ans[i] > b[i]);
}
cout << tot;
}
signed main(){
IO;
#ifdef LOCAL
freopen("inp.txt","r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
// cin >> t;
fr(tt, 1, t){
// cout << "Case #" << tt << ": ";
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2045 ms |
9856 KB |
Time limit exceeded |
2 |
Execution timed out |
2062 ms |
9572 KB |
Time limit exceeded |
3 |
Execution timed out |
2025 ms |
11888 KB |
Time limit exceeded |
4 |
Execution timed out |
2057 ms |
12132 KB |
Time limit exceeded |
5 |
Execution timed out |
2053 ms |
10984 KB |
Time limit exceeded |
6 |
Correct |
1255 ms |
10924 KB |
Output is correct |
7 |
Execution timed out |
2054 ms |
11508 KB |
Time limit exceeded |
8 |
Correct |
719 ms |
10344 KB |
Output is correct |
9 |
Correct |
1940 ms |
12140 KB |
Output is correct |
10 |
Execution timed out |
2032 ms |
12140 KB |
Time limit exceeded |