oj.uz

Submission #130639

# Submission time Handle Problem Language Result Execution time Memory
130639 2019-07-15T18:57:47 Z qkxwsm popa (BOI18_popa) C++14
100 / 100
 117 ms 460 KB 
#include <bits/stdc++.h>
#include "popa.h"

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969ll
#define MAXN 1013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N;
int ia[MAXN];

// int gcd(int a, int b)
// {
// 	return (b == 0 ? a : gcd(b, a % b));
// }
// bool query(int a, int b, int c, int d)
// {
// 	int ga = 0, gb = 0;
// 	FOR(i, a, b + 1) ga = gcd(ga, ia[i]);
// 	FOR(i, c, d + 1) gb = gcd(gb, ia[i]);
// 	return (ga == gb);
// }
int solve(int n, int *lt, int *rt)
{
	N = n;
	FOR(i, 0, N)
	{
		lt[i] = rt[i] = -1;
	}
	int root = 0;
	FOR(i, 1, N)
	{
		vi chain;
		chain.PB(root);
		while(rt[chain.back()] != -1)
		{
			chain.PB(rt[chain.back()]);
		}
		// for (int x : chain)
		// {
		// 	cerr << x << ' ';
		// }
		// cerr << endl;
		//try to insert it as low as you can.
		while(!chain.empty())
		{
			int u = chain.back();
			if (query(u, i, u, u))
			{
				lt[i] = rt[u];
				rt[u] = i;
				break;
			}
			chain.pop_back();
		}
		if (chain.empty())
		{
			lt[i] = root;
			root = i;
		}
	}
	return root;
}

// int32_t main()
// {
// 	ios_base::sync_with_stdio(0); cin.tie(0);
// 	int n; cin >> n;
// 	FOR(i, 0, n) cin >> ia[i];
// 	int ls[n + 1], rs[n + 1];
// 	int r = solve(n, ls, rs);
// 	cout << "root at " << r << '\n';
// 	FOR(i, 0, n)
// 	{
// 		if (ls[i] != -1)
// 		{
// 			cout << i << " -> " << ls[i] << endl;
// 		}
// 		if (rs[i] != -1)
// 		{
// 			cout << i << " -> " << rs[i] << endl;
// 		}
// 	}
// 	return 0;
// }

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 248 KB Output is correct
2 Correct 16 ms 248 KB Output is correct
3 Correct 13 ms 380 KB Output is correct
4 Correct 16 ms 376 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 328 KB Output is correct
2 Correct 99 ms 376 KB Output is correct
3 Correct 63 ms 332 KB Output is correct
4 Correct 96 ms 372 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 404 KB Output is correct
2 Correct 106 ms 456 KB Output is correct
3 Correct 94 ms 460 KB Output is correct
4 Correct 85 ms 340 KB Output is correct