Submission #58126

#	Time	Username	Problem	Language	Result	Execution time	Memory
58126		Benq	Crazy old lady (IZhO13_crazy)	C++14	100 / 100	74 ms	1352 KiB

crazy

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int T, N;

int comb(int a, int b) {
	if (min(a,b) == -1) return max(a,b);
	if (min(a,b) == 0) return 0;
	if (a == b) return a;
	return 0;
}

int check(vi p, int ind, int act) {
	vi P = {0};
	FOR(i,1,sz(p)) if (i != act) P.pb(i);
	P.insert(P.begin()+ind,act);
	
	bitset<1001> oc;
	FOR(i,1,sz(P)) {
		if (!oc[P[i]] && i != ind && p[i] != P[i]) return -1;
		oc[p[i]] = 1;
	}
	return act;
}

int solveX(vi p) {
	int t = -1;
	FOR(i,1,sz(p)) t = comb(t,check(p,1,i));
	return t;
}

bool verify2(vi p) {
	/*cout << "OH\n";
	for (int i: p) cout << i << " ";
	cout << "\n";*/
	if (p[1] != 2) return 0;
	int ind = 2;
	while (p[ind] == p[ind-1]+1) ind ++;
	return comb(check(p,ind,1),check(p,ind-1,1));
	// 2,3,4,5,x=1,6,7,8,9,10
	// wacky or one before wacky
}

int solve(vi p) {
	if (sz(p) == 1) return -1;
	
	if (p[1] == 1) {
		vi P(sz(p)-1);
		FOR(i,2,sz(p)) P[i-1] = p[i]-1;
		int x = solve(P);
		x = (x <= 0 ? x : x+1);
		return x;
	} else {  
		int t = solveX(p);
		if (verify2(p)) t = comb(t,1);
		return t;
	}
}

int solve() {
	cin >> N; vi p(N+1);
	FOR(i,1,N+1) cin >> p[i];
	if (N == 1) return 1;
	bool ok = 1;
	FOR(i,1,N+1) if (p[i] != i) ok = 0;
	if (ok) return 0;
	return solve(p);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> T;
	F0R(i,T) cout << solve() << "\n";
}

• Subtask 1: 100 / 100