oj.uz

Submission #112686

# Submission time Handle Problem Language Result Execution time Memory
112686 2019-05-21T12:19:04 Z BorisBarca Segway (COI19_segway) C++14
100 / 100
 867 ms 1664 KB 
/*
	$$$$$$$\                      $$\           $$$$$$$\
	$$  __$$\                     \__|          $$  __$$\
	$$ |  $$ | $$$$$$\   $$$$$$\  $$\  $$$$$$$\ $$ |  $$ | $$$$$$\   $$$$$$\   $$$$$$$\ $$$$$$\
	$$$$$$$\ |$$  __$$\ $$  __$$\ $$ |$$  _____|$$$$$$$\ | \____$$\ $$  __$$\ $$  _____|\____$$\
	$$  __$$\ $$ /  $$ |$$ |  \__|$$ |\$$$$$$\  $$  __$$\  $$$$$$$ |$$ |  \__|$$ /      $$$$$$$ |
	$$ |  $$ |$$ |  $$ |$$ |      $$ | \____$$\ $$ |  $$ |$$  __$$ |$$ |      $$ |     $$  __$$ |
	$$$$$$$  |\$$$$$$  |$$ |      $$ |$$$$$$$  |$$$$$$$  |\$$$$$$$ |$$ |      \$$$$$$$\\$$$$$$$ |
	\_______/  \______/ \__|      \__|\_______/ \_______/  \_______|\__|       \_______|\_______|
*/
#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define MP make_pair
#define INS insert
#define LB lower_bound
#define UB upper_bound
#define pii pair <int,int>
#define pll pair <long long, long long>
#define si pair<string, int>
#define is pair<int, string>
#define X first
#define Y second
#define _ << " " <<
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (a); i > (b); --i)
#define FORR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORP(i, a, b) for ((i) = (a); (i) < (b); ++i)
#define FORA(i, x) for (auto &i : x)
#define REP(i, n) FOR(i, 0, n)
#define BITS(x) __builtin_popcount(x)
#define MSET memset
#define MCPY memcpy
#define SQ(a) (a) * (a)

typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vll;
typedef vector <pll> vpl;
typedef vector <double> vd;
typedef vector <ld> vld;
typedef vector<si> vsi;
typedef vector<is> vis;
typedef vector<string> vs;
//((float) t)/CLOCKS_PER_SEC

const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int LOG = 19;
const int INF = 1e9 + 10;
const ll INFL = 1e18 + 10;
const int ABC = 30;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dox[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int doy[] = {0, 0, -1, 1, -1, 1, -1, 1};

inline int sum(int a, int b){
  if (a + b >= MOD)
  	return a + b - MOD;
  if (a + b < 0)
  	return a + b + MOD;
  return a + b;
}

inline void add(int &a, int b){
  a = sum(a, b);
}

inline int mul(int a, int b){
  return (ll)a * (ll)b % MOD;
}

inline int sub(int a, int b){
	return (a - b + MOD) % MOD;
}

inline int pot(ll pot, int n){
	ll ret = 1;
	while (n){
		if (n & 1)
			ret = (ret * pot) % MOD;
		pot = (pot * pot) % MOD;
		n >>= 1;
	}
	return ret;
}

inline int divide(int a, int b){
	return mul(a, pot(b, MOD - 2));
}

ll lcm(ll a, ll b){
	return abs(a * b) / __gcd(a, b);
}

inline double ccw(pii A, pii B, pii C){
	return (A.X * B.Y) - (A.Y * B.X) + (B.X * C.Y) - (B.Y * C.X) + (C.X * A.Y) - (C.Y * A.X);
}

inline int CCW(pii A, pii B, pii C){
	double val = ccw(A, B, C);
	double eps = max(max(abs(A.X), abs(A.Y)), max(max(abs(B.X), abs(B.Y)), max(abs(C.X), abs(C.Y)))) / 1e9;
	if (val <= -eps)
		return -1;
	if (val >= eps)
		return 1;
	return 0;
}

void to_upper(string &x){
	REP(i, sz(x))
		x[i] = toupper(x[i]);
}

void to_lower(string &x){
	REP(i, sz(x))
		x[i] = tolower(x[i]);
}

string its(ll x){
	if (x == 0)
		return "0";
	string ret = "";
	while (x > 0){
		ret += (x % 10) + '0';
		x /= 10;
	}
	reverse(all(ret));
	return ret;
}

ll sti(string s){
	ll ret = 0;
	REP(i, sz(s)){
		ret *= 10;
		ret += (s[i] - '0');
	}
	return ret;
}

const int N = 2e4 + 10;

struct player{
	int x, act;
	int speed[3];
	int ans;
} p[N]; 

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n; cin >> n;
	priority_queue <pii> pq;
	REP(i, n){
		cin >> p[i].speed[0] >> p[i].speed[1] >> p[i].speed[2];
		p[i].act = 0;
		p[i].x = 0;
		p[i].ans = 0;
		pq.push({0, i});
	}

	map <int, int> akc;
	int m; cin >> m;
	REP(i, m){
		int x; cin >> x;
		akc[x]++;
	}

	REP(x, 300){
		int ispred = 0;
		queue <pii> tmp;
		while (!pq.empty()){
			//cout << pq.top().X << '\n';
			pii st = pq.top();
			pq.pop();
			p[st.Y].ans = -st.X;
			vi pl = {st.Y};
			while (pq.top().X == st.X && !pq.empty()){
				pl.PB(pq.top().Y);
				pq.pop();
			}

			FORA(igr, pl){
				p[igr].x++;
				if (akc[x] && !p[igr].act)
					p[igr].act = (ispred % 20);
				if (p[igr].act)
					p[igr].ans++, p[igr].act--;
				else
					p[igr].ans += p[igr].speed[x / 100];
			}

			FORA(igr, pl)
				tmp.push({p[igr].ans, igr});

			ispred += sz(pl);
		}

		for (pii st = tmp.front(); !tmp.empty(); tmp.pop()) 
			pq.push({-tmp.front().X, tmp.front().Y});

	}

	REP(i, n)
		cout << p[i].ans << '\n';

	return 0;
}

Compilation message

segway.cpp: In function 'int main()':
segway.cpp:208:12: warning: variable 'st' set but not used [-Wunused-but-set-variable]
   for (pii st = tmp.front(); !tmp.empty(); tmp.pop()) 
            ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 31 ms 384 KB Output is correct
4 Correct 120 ms 512 KB Output is correct
5 Correct 862 ms 1332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 9 ms 384 KB Output is correct
10 Correct 12 ms 384 KB Output is correct
11 Correct 11 ms 384 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 31 ms 384 KB Output is correct
4 Correct 120 ms 512 KB Output is correct
5 Correct 862 ms 1332 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 8 ms 384 KB Output is correct
14 Correct 9 ms 384 KB Output is correct
15 Correct 12 ms 384 KB Output is correct
16 Correct 11 ms 384 KB Output is correct
17 Correct 39 ms 444 KB Output is correct
18 Correct 78 ms 484 KB Output is correct
19 Correct 360 ms 900 KB Output is correct
20 Correct 502 ms 1144 KB Output is correct
21 Correct 647 ms 1272 KB Output is correct
22 Correct 867 ms 1512 KB Output is correct
23 Correct 785 ms 1664 KB Output is correct