oj.uz

Submission #82212

# Submission time Handle Problem Language Result Execution time Memory
82212 2018-10-29T13:49:32 Z pamaj Doktor (COCI17_doktor) C++14
10 / 100
 1000 ms 31656 KB 
#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)
{
	return t ? t->sum : 0;
}

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 == p));
	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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 508 KB Output isn't correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 900 KB Output is correct
2 Incorrect 3 ms 900 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 1300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 6540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 31656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 31656 KB Time limit exceeded
2 Halted 0 ms 0 KB -