답안 #61428 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61428	2018-07-26T00:17:42 Z	qkxwsm	Xylophone (JOI18_xylophone)	C++17	100 / 100	166 ms	20944 KB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;

template<class T>
void readi(T &x)
{
	T input = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		input = input * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		input = -input;
	}
	x = input;
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int aout[20];
	int ilen = 0;
	while(output)
	{
		aout[ilen] = ((output % 10));
		output /= 10;
		ilen++;
	}
	for (int i = ilen - 1; i >= 0; i--)
	{
		putchar(aout[i] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long randomize(long long mod)
{
	return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}

#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-10;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 5013

long long normalize(long long x, long long mod = INF)
{
	return (((x % mod) + mod) % mod);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N;
int ans[MAXN];
int vis[MAXN][MAXN];

int get(int a, int b)
{
	if (a == b) return 0;
	if (a > b) swap(a, b);
	if (vis[a][b])
	{
		return vis[a][b];
	}
	vis[a][b] = query(a + 1, b + 1);
	return vis[a][b];
}

void solve(int n)
{
	N = n;
	ans[0] = 0;
	ans[1] = get(0, 1);
	for (int i = 2; i < N; i++)
	{
		int x = get(i - 2, i), y = get(i - 1, i);
		int u = ans[i - 1] + y, d = ans[i - 1] - y;
		int big = max(u, max(ans[i - 1], ans[i - 2]));
		int small = min(u, min(ans[i - 1], ans[i - 2]));
		if (big - small == x)
		{
			ans[i] = u;
		}
		else
		{
			ans[i] = d;
		}
	}
	int sm = INF;
	for (int i = 0; i < N; i++)
	{
		ckmin(sm, ans[i]);
	}
	for (int i = 0; i < N; i++)
	{
		ans[i] -= sm;
	}
	bool flag = false;
	for (int i = 0; i < N; i++)
	{
		if (ans[i] == 0)
		{
			break;
		}
		if (ans[i] == N - 1)
		{
			flag = true;
			break;
		}
	}
	if (flag)
	{
		for (int i = 0; i < N; i++)
		{
			ans[i] = (N - 1) - ans[i];
		}
	}
//	cerr << lo << ' ' << hi << endl;
	for (int i = 0; i < N; i++)
	{
		answer(i + 1, ans[i] + 1);
	}
}

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	4 ms	516 KB	Output is correct
4	Correct	6 ms	848 KB	Output is correct
5	Correct	5 ms	892 KB	Output is correct
6	Correct	4 ms	912 KB	Output is correct
7	Correct	3 ms	912 KB	Output is correct
8	Correct	7 ms	912 KB	Output is correct
9	Correct	5 ms	912 KB	Output is correct
10	Correct	4 ms	912 KB	Output is correct
11	Correct	6 ms	912 KB	Output is correct
12	Correct	4 ms	912 KB	Output is correct
13	Correct	5 ms	912 KB	Output is correct
14	Correct	5 ms	952 KB	Output is correct
15	Correct	5 ms	952 KB	Output is correct

Subtask #2
36.0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	4 ms	516 KB	Output is correct
4	Correct	6 ms	848 KB	Output is correct
5	Correct	5 ms	892 KB	Output is correct
6	Correct	4 ms	912 KB	Output is correct
7	Correct	3 ms	912 KB	Output is correct
8	Correct	7 ms	912 KB	Output is correct
9	Correct	5 ms	912 KB	Output is correct
10	Correct	4 ms	912 KB	Output is correct
11	Correct	6 ms	912 KB	Output is correct
12	Correct	4 ms	912 KB	Output is correct
13	Correct	5 ms	912 KB	Output is correct
14	Correct	5 ms	952 KB	Output is correct
15	Correct	5 ms	952 KB	Output is correct
16	Correct	11 ms	1464 KB	Output is correct
17	Correct	10 ms	2488 KB	Output is correct
18	Correct	22 ms	3896 KB	Output is correct
19	Correct	25 ms	4540 KB	Output is correct
20	Correct	35 ms	4540 KB	Output is correct
21	Correct	35 ms	4540 KB	Output is correct
22	Correct	16 ms	4616 KB	Output is correct
23	Correct	23 ms	4616 KB	Output is correct
24	Correct	27 ms	4616 KB	Output is correct
25	Correct	25 ms	4616 KB	Output is correct
26	Correct	21 ms	4616 KB	Output is correct
27	Correct	23 ms	4616 KB	Output is correct
28	Correct	19 ms	4616 KB	Output is correct
29	Correct	21 ms	4616 KB	Output is correct
30	Correct	34 ms	4616 KB	Output is correct

Subtask #3
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	4 ms	516 KB	Output is correct
4	Correct	6 ms	848 KB	Output is correct
5	Correct	5 ms	892 KB	Output is correct
6	Correct	4 ms	912 KB	Output is correct
7	Correct	3 ms	912 KB	Output is correct
8	Correct	7 ms	912 KB	Output is correct
9	Correct	5 ms	912 KB	Output is correct
10	Correct	4 ms	912 KB	Output is correct
11	Correct	6 ms	912 KB	Output is correct
12	Correct	4 ms	912 KB	Output is correct
13	Correct	5 ms	912 KB	Output is correct
14	Correct	5 ms	952 KB	Output is correct
15	Correct	5 ms	952 KB	Output is correct
16	Correct	11 ms	1464 KB	Output is correct
17	Correct	10 ms	2488 KB	Output is correct
18	Correct	22 ms	3896 KB	Output is correct
19	Correct	25 ms	4540 KB	Output is correct
20	Correct	35 ms	4540 KB	Output is correct
21	Correct	35 ms	4540 KB	Output is correct
22	Correct	16 ms	4616 KB	Output is correct
23	Correct	23 ms	4616 KB	Output is correct
24	Correct	27 ms	4616 KB	Output is correct
25	Correct	25 ms	4616 KB	Output is correct
26	Correct	21 ms	4616 KB	Output is correct
27	Correct	23 ms	4616 KB	Output is correct
28	Correct	19 ms	4616 KB	Output is correct
29	Correct	21 ms	4616 KB	Output is correct
30	Correct	34 ms	4616 KB	Output is correct
31	Correct	58 ms	9344 KB	Output is correct
32	Correct	72 ms	13056 KB	Output is correct
33	Correct	115 ms	18212 KB	Output is correct
34	Correct	140 ms	20796 KB	Output is correct
35	Correct	151 ms	20856 KB	Output is correct
36	Correct	80 ms	20856 KB	Output is correct
37	Correct	95 ms	20856 KB	Output is correct
38	Correct	118 ms	20856 KB	Output is correct
39	Correct	129 ms	20856 KB	Output is correct
40	Correct	106 ms	20896 KB	Output is correct
41	Correct	127 ms	20896 KB	Output is correct
42	Correct	97 ms	20896 KB	Output is correct
43	Correct	139 ms	20896 KB	Output is correct
44	Correct	81 ms	20928 KB	Output is correct
45	Correct	95 ms	20928 KB	Output is correct
46	Correct	147 ms	20928 KB	Output is correct
47	Correct	91 ms	20928 KB	Output is correct
48	Correct	166 ms	20928 KB	Output is correct
49	Correct	116 ms	20928 KB	Output is correct
50	Correct	91 ms	20928 KB	Output is correct
51	Correct	124 ms	20928 KB	Output is correct
52	Correct	85 ms	20928 KB	Output is correct
53	Correct	113 ms	20928 KB	Output is correct
54	Correct	123 ms	20928 KB	Output is correct
55	Correct	122 ms	20928 KB	Output is correct
56	Correct	127 ms	20944 KB	Output is correct
57	Correct	138 ms	20944 KB	Output is correct
58	Correct	129 ms	20944 KB	Output is correct
59	Correct	128 ms	20944 KB	Output is correct
60	Correct	107 ms	20944 KB	Output is correct

답안 #61428

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 36.0 / 36.0

Subtask #3 53.0 / 53.0

Subtask #1
11.0 / 11.0

Subtask #2
36.0 / 36.0

Subtask #3
53.0 / 53.0