oj.uz

답안 #84480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
84480 2018-11-15T12:19:54 Z bogdan10bos Xylophone (JOI18_xylophone) C++14
0 / 100
 1 ms 760 KB 
#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

map<int, int> mp[10005];
int v[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;
}

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

    int st = 1;
    int p = 1, u = N;
    while(p <= u)
    {
        int mij = p + (u - p) / 2;
        if( myquery(mij, N) == N - 1 )
            st = mij, p = mij + 1;
        else
            u = mij - 1;
    }

    answer(st, 1);  v[st] = 1;

    if(st > 1)
    {
        int d = myquery(st - 1, st);
        answer(st - 1, d + 1); v[st - 1] = d + 1;

        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))
            {
                answer(i, x - dx);
                v[i] = x - dx;
            }
            else
            {
                answer(i, x + dx);
                v[i] = x + dx;
            }
        }
    }

    if(st + 1 < N)
    {
        int d = myquery(st, st + 1);
        answer(st + 1, d + 1); v[st + 1] = d + 1;

        for(int i = st + 2; i <= N; 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))
            {
                answer(i, x - dx);
                v[i] = x - dx;
            }
            else
            {
                answer(i, x + dx);
                v[i] = x + dx;
            }
        }
    }
}

#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;
}

int main() {
    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
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 760 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 760 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 760 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -