답안 #84481 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
84481	2018-11-15T12:22:06 Z	bogdan10bos	Xylophone (JOI18_xylophone)	C++14	100 / 100	480 ms	1660 KB

xylophone

#include <bits/stdc++.h>

//#define DEBUG

#ifndef DEBUG
#include "xylophone.h"
#endif

using namespace std;

#ifdef DEBUG
int query(int s, int t);
void answer(int i, int a);
#endif

namespace MyCode
{
    int NN;

    map<int, int> mp[10005];
    int v[10005], f[10005];

    int myquery(int st, int dr)
    {
        if(st == dr)    return 0;
        if(st > dr) return -1;
        if(mp[st].count(dr))    return mp[st][dr];
        mp[st][dr] = query(st, dr);
        return mp[st][dr];
    }

    bool valid(int x, int y, int z, int dxz)
    {
        int mx = max({x, y, z});
        int mn = min({x, y, z});
        return (mx - mn) == dxz;
    }

    bool setval(int x, int y)
    {
        if(y < 1 || NN < y)  return false;
        if(x < 1 || NN < x)  return false;
        if(f[y])    return false;
        if(v[x])    return false;
        v[x] = y;
        f[y] = x;
        return true;
    }

    bool can(int p1)
    {
        for(int i = 1; i <= NN; i++) v[i] = f[i] = 0;

        int st = p1;
        if( !setval(st, 1) )    return false;

        if(st > 1)
        {
            int d = myquery(st - 1, st);
            if(!setval(st - 1, d + 1))  return false;

            for(int i = st - 2; i >= 1; i--)
            {
                int x = v[i + 1], y = v[i + 2];

                int dx = myquery(i, i + 1);
                int dy = myquery(i, i + 2);

                if(valid(x - dx, x, y, dy))
                {
                    if(!setval(i, x - dx))  return false;
                }
                else
                {
                    if(!setval(i, x + dx))  return false;
                }
            }
        }

        if(st + 1 <= NN)
        {
            int d = myquery(st, st + 1);
            if(!setval(st + 1, d + 1))  return false;

            for(int i = st + 2; i <= NN; i++)
            {
                int x = v[i - 1], y = v[i - 2];

                int dx = myquery(i - 1, i);
                int dy = myquery(i - 2, i);

                if(valid(x - dx, x, y, dy))
                {
                    if(!setval(i, x - dx))  return false;
                }
                else
                {
                    if(!setval(i, x + dx))  return false;
                }
            }
        }

        return true;
    }

    void solve(int N)
    {
        NN = N;
        for(int i = 1; i <= NN; i++) mp[i].clear();
        for(int i = 1; i <= NN; i++) v[i] = 0;

        for(int i = 1; i <= NN; i++)
            if(can(i))
            {
                for(int i = 1; i <= NN; i++)
                    answer(i, v[i]);
                return;
            }
    }
}

void solve(int N)
{
    MyCode::solve(N);
}

#ifdef DEBUG
static const int N_MAX = 5000;
static const int Q_MAX = 20000;
static int N;
static int A[N_MAX];
static bool used[N_MAX];
static int query_c;
static int answer_c;

int query(int s, int t) {
	if(query_c >= Q_MAX) {
		printf("Wrong Answer\n");
		exit(0);
	}
	query_c++;
	if(!(1 <= s && s <= t && t <= N)) {
		printf("Wrong Answer\n");
		exit(0);
	}
	int mx = 0, mn = N + 1;
	for(int i = s - 1; i < t; i++) {
		if(mx < A[i]) {
			mx = A[i];
		}
		if(mn > A[i]) {
			mn = A[i];
		}
	}
	return mx - mn;
}

void answer(int i, int a) {
	answer_c++;
	if(!(1 <= i && i <= N)) {
		printf("Wrong Answer\n");
		exit(0);
	}
	if(!(1 <= a && a <= N)) {
		printf("Wrong Answer\n");
		exit(0);
	}
	if(used[i - 1]) {
		printf("Wrong Answer\n");
		exit(0);
	}
	if(a != A[i - 1]) {
		printf("Wrong Answer\n");
		exit(0);
	}
	used[i - 1] = true;
}

void gen()
{
    freopen("1.in", "w", stdout);
    int N = 5000;
    printf("%d\n", N);
    vector<int> p;
    for(int i = 1; i <= N; i++) p.push_back(i);

    mt19937 g(chrono::high_resolution_clock::now().time_since_epoch().count());
    shuffle(p.begin(), p.end(), g);

    int p1 = 0, pn = 0;
    for(int i = 0; i < N; i++)
    {
        if(p[i] == 1)   p1 = i;
        if(p[i] == N)   pn = i;
    }
    if(p1 > pn) swap(p[p1], p[pn]);

    for(auto x: p)  printf("%d ", x);
    exit(0);
}

int main() {
    //gen();
    freopen("1.in", "r", stdin);
	query_c = 0;
	answer_c = 0;
	if(scanf("%d", &N) != 1) {
		fprintf(stderr, "Error while reading input\n");
		exit(1);
	}
	for(int i = 0; i < N; i++) {
		if(scanf("%d", A + i) != 1) {
			fprintf(stderr, "Error while reading input\n");
			exit(1);
		}
		used[i] = false;
	}
	solve(N);
	if(!(answer_c == N)) {
		printf("Wrong Answer\n");
		exit(0);
	}
	printf("Accepted : %d\n", query_c);
}
#endif

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	760 KB	Output is correct
2	Correct	2 ms	760 KB	Output is correct
3	Correct	8 ms	1000 KB	Output is correct
4	Correct	4 ms	1000 KB	Output is correct
5	Correct	4 ms	1000 KB	Output is correct
6	Correct	4 ms	1008 KB	Output is correct
7	Correct	4 ms	1008 KB	Output is correct
8	Correct	3 ms	1008 KB	Output is correct
9	Correct	4 ms	1052 KB	Output is correct
10	Correct	4 ms	1052 KB	Output is correct
11	Correct	4 ms	1052 KB	Output is correct
12	Correct	3 ms	1052 KB	Output is correct
13	Correct	3 ms	1052 KB	Output is correct
14	Correct	4 ms	1052 KB	Output is correct
15	Correct	3 ms	1056 KB	Output is correct

Subtask #2
36.0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	760 KB	Output is correct
2	Correct	2 ms	760 KB	Output is correct
3	Correct	8 ms	1000 KB	Output is correct
4	Correct	4 ms	1000 KB	Output is correct
5	Correct	4 ms	1000 KB	Output is correct
6	Correct	4 ms	1008 KB	Output is correct
7	Correct	4 ms	1008 KB	Output is correct
8	Correct	3 ms	1008 KB	Output is correct
9	Correct	4 ms	1052 KB	Output is correct
10	Correct	4 ms	1052 KB	Output is correct
11	Correct	4 ms	1052 KB	Output is correct
12	Correct	3 ms	1052 KB	Output is correct
13	Correct	3 ms	1052 KB	Output is correct
14	Correct	4 ms	1052 KB	Output is correct
15	Correct	3 ms	1056 KB	Output is correct
16	Correct	5 ms	1056 KB	Output is correct
17	Correct	11 ms	1100 KB	Output is correct
18	Correct	20 ms	1100 KB	Output is correct
19	Correct	17 ms	1228 KB	Output is correct
20	Correct	19 ms	1228 KB	Output is correct
21	Correct	21 ms	1228 KB	Output is correct
22	Correct	19 ms	1228 KB	Output is correct
23	Correct	14 ms	1228 KB	Output is correct
24	Correct	33 ms	1228 KB	Output is correct
25	Correct	17 ms	1228 KB	Output is correct
26	Correct	20 ms	1228 KB	Output is correct
27	Correct	13 ms	1228 KB	Output is correct
28	Correct	17 ms	1228 KB	Output is correct
29	Correct	20 ms	1228 KB	Output is correct
30	Correct	18 ms	1228 KB	Output is correct

Subtask #3
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	760 KB	Output is correct
2	Correct	2 ms	760 KB	Output is correct
3	Correct	8 ms	1000 KB	Output is correct
4	Correct	4 ms	1000 KB	Output is correct
5	Correct	4 ms	1000 KB	Output is correct
6	Correct	4 ms	1008 KB	Output is correct
7	Correct	4 ms	1008 KB	Output is correct
8	Correct	3 ms	1008 KB	Output is correct
9	Correct	4 ms	1052 KB	Output is correct
10	Correct	4 ms	1052 KB	Output is correct
11	Correct	4 ms	1052 KB	Output is correct
12	Correct	3 ms	1052 KB	Output is correct
13	Correct	3 ms	1052 KB	Output is correct
14	Correct	4 ms	1052 KB	Output is correct
15	Correct	3 ms	1056 KB	Output is correct
16	Correct	5 ms	1056 KB	Output is correct
17	Correct	11 ms	1100 KB	Output is correct
18	Correct	20 ms	1100 KB	Output is correct
19	Correct	17 ms	1228 KB	Output is correct
20	Correct	19 ms	1228 KB	Output is correct
21	Correct	21 ms	1228 KB	Output is correct
22	Correct	19 ms	1228 KB	Output is correct
23	Correct	14 ms	1228 KB	Output is correct
24	Correct	33 ms	1228 KB	Output is correct
25	Correct	17 ms	1228 KB	Output is correct
26	Correct	20 ms	1228 KB	Output is correct
27	Correct	13 ms	1228 KB	Output is correct
28	Correct	17 ms	1228 KB	Output is correct
29	Correct	20 ms	1228 KB	Output is correct
30	Correct	18 ms	1228 KB	Output is correct
31	Correct	50 ms	1232 KB	Output is correct
32	Correct	63 ms	1360 KB	Output is correct
33	Correct	65 ms	1580 KB	Output is correct
34	Correct	106 ms	1580 KB	Output is correct
35	Correct	101 ms	1580 KB	Output is correct
36	Correct	74 ms	1660 KB	Output is correct
37	Correct	465 ms	1660 KB	Output is correct
38	Correct	63 ms	1660 KB	Output is correct
39	Correct	96 ms	1660 KB	Output is correct
40	Correct	98 ms	1660 KB	Output is correct
41	Correct	91 ms	1660 KB	Output is correct
42	Correct	77 ms	1660 KB	Output is correct
43	Correct	480 ms	1660 KB	Output is correct
44	Correct	74 ms	1660 KB	Output is correct
45	Correct	75 ms	1660 KB	Output is correct
46	Correct	79 ms	1660 KB	Output is correct
47	Correct	71 ms	1660 KB	Output is correct
48	Correct	72 ms	1660 KB	Output is correct
49	Correct	79 ms	1660 KB	Output is correct
50	Correct	110 ms	1660 KB	Output is correct
51	Correct	50 ms	1660 KB	Output is correct
52	Correct	112 ms	1660 KB	Output is correct
53	Correct	87 ms	1660 KB	Output is correct
54	Correct	81 ms	1660 KB	Output is correct
55	Correct	73 ms	1660 KB	Output is correct
56	Correct	82 ms	1660 KB	Output is correct
57	Correct	80 ms	1660 KB	Output is correct
58	Correct	117 ms	1660 KB	Output is correct
59	Correct	73 ms	1660 KB	Output is correct
60	Correct	106 ms	1660 KB	Output is correct

답안 #84481

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