Submission #84481

#	Time	Username	Problem	Language	Result	Execution time	Memory
84481		bogdan10bos	Xylophone (JOI18_xylophone)	C++14	100 / 100	480 ms	1660 KiB

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 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53