Submission #649470

#	Time	Username	Problem	Language	Result	Execution time	Memory
649470		BackNoob	Xylophone (JOI18_xylophone)	C++14	100 / 100	165 ms	568 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

int n;
int a[mxN];
int ans[mxN];
int d2[mxN];
int d3[mxN];
int sign[mxN];
bool vis[mxN];

//int query(int l, int r)
//{
//    int lef = inf;
//    int rig = -inf;
//    for(int i = l; i <= r; i++) {
//        minimize(lef, a[i]);
//        maximize(rig, a[i]);
//    }
//    return rig - lef;
//}
//
//void answer(int i, int x)
//{
//    cout << x << ' ';
//}

bool ispermutation()
{
    for(int i = 1; i <= n; i++) vis[i] = false;
    for(int i = 1; i <= n; i++) {
        if(ans[i] < 1 || ans[i] > n) return false;
        if(vis[ans[i]] == true) return false;
        vis[ans[i]] = true;
    }
    int lef, rig;
    for(int i = 1; i <= n; i++) {
        if(ans[i] == 1) lef = i;
        if(ans[i] == n) rig = i;
    }
    return lef < rig;
}

bool calc(int cur)
{
    for(int x = 1; x <= n; x++) {
        ans[1] = x;
        for(int i = 2; i <= n; i++) {
            cur ^= sign[i - 1];
            if(cur == 1) ans[i] = ans[i - 1] + d2[i - 1];
            else ans[i] = ans[i - 1] - d2[i - 1];
        }
        if(ispermutation() == true) return true;
    }
    return false;
}

void solve(int _n)
{
    n = _n;
//    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i + 1 <= n; i++) d2[i] = query(i, i + 1);
    for(int i = 1; i + 2 <= n; i++) d3[i] = query(i, i + 2);


    sign[1] = 0;
    for(int i = 1; i + 2 <= n; i++) {
        if(d2[i] + d2[i + 1] == d3[i]) sign[i + 1] = 0;
        else sign[i + 1] = 1;
    }


    if(calc(0) == false) calc(1);
    for(int i = 1; i <= n; i++) answer(i, ans[i]);

//    for(int i = 1; i + 2 <= n; i++) {
//        if(d3[i] != max({ans[i], ans[i + 1], ans[i + 2]}) - min({ans[i], ans[i + 1], ans[i + 2]})) cout << "error" << endl;
//    }
}

//int main()
//{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    freopen(TASK".inp" , "r" , stdin);
//    freopen(TASK".out" , "w" , stdout);
//
//
//    int tc = 1;
//    //cin >> tc;
//    while(tc--) {
//        int x;
//        cin >> x;
//    	solve(x);
//    }
//    return 0;
//}

Compilation message (stderr)

xylophone.cpp: In function 'bool ispermutation()':
xylophone.cpp:68:18: warning: 'rig' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |     return lef < rig;
      |                  ^~~
xylophone.cpp:68:18: warning: 'lef' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53