답안 #106352

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106352 2019-04-18T02:47:16 Z aviroop123 Kralj (COCI16_kralj) C++14
56 / 140
2000 ms 12260 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));
	reverse(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 < b[p] && val < ans[p]){
				swap(ans[p], val);
			}
			p++;
			if(p == n) p = 0;
		}
		ans[p] = val;
		debug(ans);
	}
	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;
}

Compilation message

kralj.cpp: In function 'void solve()':
kralj.cpp:126:13: warning: statement has no effect [-Wunused-value]
   debug(ans);
             ^
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2041 ms 9828 KB Time limit exceeded
2 Execution timed out 2048 ms 9700 KB Time limit exceeded
3 Execution timed out 2074 ms 11872 KB Time limit exceeded
4 Execution timed out 2059 ms 12260 KB Time limit exceeded
5 Execution timed out 2068 ms 11080 KB Time limit exceeded
6 Correct 1274 ms 11124 KB Output is correct
7 Execution timed out 2050 ms 11620 KB Time limit exceeded
8 Correct 812 ms 10468 KB Output is correct
9 Correct 1821 ms 12260 KB Output is correct
10 Correct 1950 ms 12256 KB Output is correct