Submission #58126

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58126	2018-07-16T23:36:12 Z	Benq	Crazy old lady (IZhO13_crazy)	C++14	100 / 100	74 ms	1352 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	3 ms	604 KB	Output is correct
4	Correct	4 ms	736 KB	Output is correct
5	Correct	3 ms	808 KB	Output is correct
6	Correct	3 ms	808 KB	Output is correct
7	Correct	4 ms	808 KB	Output is correct
8	Correct	8 ms	808 KB	Output is correct
9	Correct	10 ms	856 KB	Output is correct
10	Correct	12 ms	1012 KB	Output is correct
11	Correct	15 ms	1044 KB	Output is correct
12	Correct	17 ms	1044 KB	Output is correct
13	Correct	24 ms	1044 KB	Output is correct
14	Correct	26 ms	1048 KB	Output is correct
15	Correct	32 ms	1072 KB	Output is correct
16	Correct	36 ms	1072 KB	Output is correct
17	Correct	39 ms	1136 KB	Output is correct
18	Correct	56 ms	1304 KB	Output is correct
19	Correct	50 ms	1304 KB	Output is correct
20	Correct	74 ms	1352 KB	Output is correct