oj.uz

Submission #135029

# Submission time Handle Problem Language Result Execution time Memory
135029 2019-07-23T14:37:50 Z osaaateiasavtnl Xylophone (JOI18_xylophone) C++14
0 / 100
 4 ms 408 KB 
#include<bits/stdc++.h>
using namespace std;
#ifdef HOME
#else
#include "xylophone.h"
#endif

const int N = 5001;

#ifdef HOME
const int INF = 1e9 + 7;
int n;
int a[N];
int query(int l, int r) {
    int mn = INF, mx = -INF;
    for (int i = l; i <= r; ++i) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }   
    return mx - mn;
}   
void answer(int i, int x) {

}   
#endif

int ans[N];
int mem[2][N];
bool t[N], r[N];
int cnt[N];
bool check(int n) {
    for (int i = 1; i <= n; ++i) {
        if (ans[i] < 1 || ans[i] > n) return 0;
    }   
    for (int i = 1; i <= n; ++i) {
        cnt[i] = 0;
    }   
    for (int i = 1; i <= n; ++i) {
        ++cnt[ans[i]];
    }   
    for (int i = 1; i <= n; ++i) {
        if (cnt[i] != 1) {
            return 0;
        }
    }   
    return 1;
}   
void solve(int n) {
    for (int i = 1; i + 1 <= n; ++i) {
        mem[0][i] = query(i, i + 1);
    }           
    for (int i = 1; i + 2 <= n; ++i) {
        mem[1][i] = query(i, i + 2);
    }   
    for (int i = 1; i + 2 <= n; ++i) {
        t[i + 2] = (mem[0][i] + mem[0][i + 1]) != mem[1][i];
    }   
    for (int i = 1; i <= n; ++i) {
        r[i] = r[i - 1] ^ t[i];
    }
    #ifdef HOME
    for (int i = 1; i <= n; ++i) {
        cout << r[i] << ' ';
    }   
    cout << '\n';
    #endif
    for (int f = 1; f <= n; ++f) {
        ans[1] = f;
        for (int i = 2; i <= n; ++i) {
            if (r[i]) {
                ans[i] = ans[i - 1] + mem[0][i - 1];
            }   
            else {
                ans[i] = ans[i - 1] - mem[0][i - 1];
            }   
        }   
        if (check(n)) {
            for (int i = 1; i <= n; ++i) {
                answer(i, ans[i]);
            }   
            return;
        }   
        ans[1] = f;
        for (int i = 2; i <= n; ++i) {
            if (r[i]) {
                ans[i] = ans[i - 1] - mem[0][i - 1];
            }   
            else {
                ans[i] = ans[i - 1] + mem[0][i - 1];
            }   
        }   
        if (check(n)) {
            for (int i = 1; i <= n; ++i) {
                answer(i, ans[i]);
            }   
            return;
        }   
    }
}   
#ifdef HOME
signed main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }   
    solve(n);
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << ' ';
    }   
    cout << '\n';
}   
#endif

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 3 ms 248 KB Output is correct
4 Correct 3 ms 404 KB Output is correct
5 Correct 4 ms 248 KB Output is correct
6 Correct 4 ms 248 KB Output is correct
7 Incorrect 3 ms 408 KB Wrong Answer [7]
8 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 3 ms 248 KB Output is correct
4 Correct 3 ms 404 KB Output is correct
5 Correct 4 ms 248 KB Output is correct
6 Correct 4 ms 248 KB Output is correct
7 Incorrect 3 ms 408 KB Wrong Answer [7]
8 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 3 ms 248 KB Output is correct
4 Correct 3 ms 404 KB Output is correct
5 Correct 4 ms 248 KB Output is correct
6 Correct 4 ms 248 KB Output is correct
7 Incorrect 3 ms 408 KB Wrong Answer [7]
8 Halted 0 ms 0 KB -