Submission #26721

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26721	2017-07-05T10:23:51 Z	model_code	Tree Rotations (POI11_rot)	C++11	27 / 100	759 ms	44908 KB

/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Rotacje na drzewie                               *
 *   Autor:             Adam Karczmarz                                   *
 *   Opis:              Rozwiazanie bledne                               *
 *                      rozwazanie czesci par                            *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <set>
#include <vector>

#define REP(AA,BB) for(AA=0; AA<(BB); ++AA)
#define FOR(AA,BB,CC) for(AA=BB; AA<(CC); ++AA)
#define FC(AA,BB) for(auto BB=AA.begin(); BB!=AA.end(); ++BB)

int WSP;

using namespace std;

struct node;
struct node {
	node *left, *right; int v;
	set<int> *st;
	node() { left=right=0; st=0; }
};

int f;
// wczytywanie danych
void read_input(node *tr) {
	int c; f=scanf("%d", &c);
	if(c!=0) {
		tr->st=new set<int>;
		tr->v=c; tr->st->insert(c);
	}
	else {
		tr->left=new node; tr->right=new node;
		read_input(tr->left); read_input(tr->right);
	}
}

int cmp(set<int> *a, set<int> *b) {
	int sw=0;
	if(a->size()>b->size()) {
		swap(a,b);
		sw=1;
	}
	set<int>::iterator it=a->begin(), jt=b->begin();
	int x=0, y=0, lim=a->size()*WSP; long long inv=0LL;
	for(; it!=a->end() && jt!=b->end() && y<=lim; ) {
		if(*it<*jt) {
			inv+=y;
			++it; ++x;
		}
		else {
			++jt; ++y;
		}
	}
	for(; it!=a->end(); ) {
		++it; ++x;
		inv+=y;
	}
	for(; jt!=b->end() && y<=lim; ) {
		++jt; ++y;
	}
	return sw ? inv>=(long long)x*y-inv : inv<=(long long)x*y-inv;
}

// rotacja na podstawie porządku leksykograficznego
// zbiorow lisci w poddrzewie
void rotate(node *tr) {
	if(tr->left==0)
		return;
	rotate(tr->left); rotate(tr->right);
	if(!cmp(tr->left->st, tr->right->st))
		swap(tr->left, tr->right);
	if(tr->left->st->size()<=tr->right->st->size()) {
		tr->st=tr->right->st;
		FC((*tr->left->st),it)
			tr->st->insert(*it);
		delete tr->left->st;
	}
	else {
		tr->st=tr->left->st;
		FC((*tr->right->st),it)
			tr->st->insert(*it);
		delete tr->right->st;
	}
}

vector<int> perm, tmp;

void generate(node *tr) {
	if(tr->left==0) {
		perm.push_back(tr->v);
		return;
	}
	generate(tr->left);
	generate(tr->right);
}

long long compute(int l, int r) {
	if(l==r)
		return 0;
	int i, j, k, mid=(l+r)/2; 
	long long res=compute(l,mid)+compute(mid+1,r);
	tmp.clear();
	for(i=l, j=mid+1, k=0; i<=mid && j<=r; ) {
		if(perm[i]<perm[j]) {
			res+=k;
			tmp.push_back(perm[i++]);
		}
		else {
			++k;
			tmp.push_back(perm[j++]);
		}
	}
	for(; i<=mid; ++i) {
		tmp.push_back(perm[i]);
		res+=k;
	}
	for(; j<=r; ++j)
		tmp.push_back(perm[j]);
	REP(i,(int)tmp.size())
		perm[l+i]=tmp[i];
	return res;
}

int main(void) {
	node *root=new node; int n;
	f=scanf("%d", &n); read_input(root);  WSP=10000000/n;
	rotate(root); generate(root);
	printf("%lld\n", compute(0, n-1));
	return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	1176 KB	Output is correct
2	Correct	1176 KB	Output is correct
3	Correct	1176 KB	Output is correct
4	Correct	1176 KB	Output is correct
5	Correct	1176 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	1176 KB	Output is correct
2	Correct	1176 KB	Output is correct
3	Correct	1176 KB	Output is correct
4	Correct	1176 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1308 KB	Output is correct
2	Correct	0 ms	1440 KB	Output is correct
3	Correct	0 ms	1440 KB	Output is correct
4	Correct	3 ms	1440 KB	Output is correct

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 10.0

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

Submission #26721

Compilation message