Submission #82217

#	Time	Username	Problem	Language	Result	Execution time	Memory
82217		pamaj	Doktor (COCI17_doktor)	C++14	0 / 100	4 ms	1000 KiB

doktor

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;

random_device rnd;
mt19937 rd(random_device{}());

struct node
{
	int v, w, sz, sum;
	node *l, *r;
	bool rev;
	node(int v_ = 0)
	{
		v = sum = v_;
		w = rd();
		sz = 1;
		l = r = nullptr;
		rev = false;
	}
};

inline int sz(node *t)
{
	return t ? t->sz : 0;
}

inline int sum(node *t, int p = 0)
{
	if(!t) return 0;

	int suml = sum(t->r, p + t -> r -> sz + 1);
	int sumr = sum(t -> l, p);

	return ((t -> l -> sz + 1) == t->v) + suml + sumr;
}

inline void flush(node *t)
{
	if(!t || !t->rev) return;
	swap(t->l, t->r);
	if(t->l) t->l->rev ^= 1;
	if(t->r) t->r->rev ^= 1;
}

inline void update(node *t)
{
	if(t == nullptr) return;
	t->sz = sz(t->l) + sz(t->r) + 1;
	t->sum = sum(t->l) + sum(t->r) + t->v;
}

inline void merge(node*& t, node *l, node *r)
{
	if(!l || !r) return void(t = l?l:r);
	flush(l), flush(r);

	if(l->w >= r->w)
	{
		merge(l->r, l->r, r);
		t = l;
	}
	else
	{
		merge(r->l, l, r->l);
		t = r;
	}
	update(t);
}

inline void split(node *t, node*& l, node*& r, int p)
{
	if(!t) return void(l = r = nullptr);
	flush(t);

	int pos = sz(t->l) + 1;
	if(pos < p)
	{
		l = t;
		split(t->r, t->r, r, p-pos);
	}
	else
	{
		r = t;
		split(t->l, l, t->l, p);
	}
	update(t);
}

inline void insert(node*& t, int p, int v)
{
	node *l = 0, *r = 0, *aux = new node(v);
	split(t, l, r, p);
	merge(l, l, aux);
	merge(t, l, r);
}

inline void reverse(node*& t, int l, int r)
{
	node *a = 0, *b = 0, *aux = 0;
	split(t, a, b, r+1);
	split(a, aux, a, l);
	a->rev ^= 1;
	merge(a, aux, a);
	merge(t, a, b);
}

ostream& operator<<(ostream& out, node *t)
{
	flush(t);
	if(t) out << t->l << t->v << " " << t->r;
	return out;
}

int v[maxn], pfsum[maxn] , n;
int pos[maxn];

int main()
{
	node *t=0;

	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		v[i] = x;
		insert(t, i, x);
		pos[v[i]] = i;
		if(v[i] == i) pfsum[i] = pfsum[i - 1] + 1;
	}
	
	vector<pair<int, int>> p;

	for(int i = 1; i <= n; i++)
	{
		if(v[i] == i) continue;
		int ini = v[i], fim = pos[v[i]];
		if(ini > fim) swap(ini, fim);
		p.push_back({ini, fim});
	}

	int best = 0;
	pair<int, int> bp;
	for(auto u : p)
	{

		int ans = 0;
		int i = u.first, j = u.second;
		ans += pfsum[i - 1];
		ans += pfsum[n] - pfsum[j];

		int mid = (u.second - u.first)/2;
		reverse(t, u.first, u.second);
		for(int z = u.first; z <= u.second; z++)
		{
			if(v[z] == z) ans++;
		}
		if(ans >= best)
		{
			best = ans;
			bp.first = v[u.first], bp.second = v[u.second];
		}
	}

	//cout << best << "\n";
	if(bp.first == 0 and bp.second == 0) 
	{
		for(int i = 1; i <= n; i++)
		{
			if(v[i] == i) cout << i << " " << i << "\n";
			return 0;		
		}
	}

	cout << bp.first << " " << bp.second << "\n";
}

Compilation message (stderr)

doktor.cpp: In function 'int main()':
doktor.cpp:155:7: warning: unused variable 'mid' [-Wunused-variable]
   int mid = (u.second - u.first)/2;
       ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10