oj.uz

Submission #30094

# Submission time Handle Problem Language Result Execution time Memory
30094 2017-07-22T05:55:49 Z 김동현(#1246) Tree Rotations (POI11_rot) C++14
0 / 100
 1000 ms 21776 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, a[400010], c = 1, lc[400010], rc[400010];
ll ans;

vector<int> f(int r){
	if(a[c]){
		vector<int> ret;
		ret.push_back(a[c]);
		return ret;
	}
	vector<int> lv = f(++c);
	vector<int> rv = f(++c);
	vector<int> ret;
	ll li = 0, ri = 0;
	for(int i = 0, j = 0; i < lv.size() || j < rv.size(); ){
		if(i == lv.size()){
			li += int(rv.size());
			ret.push_back(rv[j++]);
		}
		else if(j == rv.size()){
			ri += int(rv.size());
			ret.push_back(lv[i++]);
		}
		else{
			if(lv[i] < rv[j]){
				ri += j;
				ret.push_back(lv[i++]);
			}
			else{
				li += i;
				ret.push_back(rv[j++]);
			}
		}
	}
	ans += min(li, ri);
	return ret;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i < 2 * n; i++) scanf("%d", a + i);
	f(1);
	printf("%lld\n", ans);
}

Compilation message

rot.cpp: In function 'std::vector<int> f(int)':
rot.cpp:18:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0, j = 0; i < lv.size() || j < rv.size(); ){
                          ^
rot.cpp:18:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0, j = 0; i < lv.size() || j < rv.size(); ){
                                           ^
rot.cpp:19:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == lv.size()){
        ^
rot.cpp:23:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(j == rv.size()){
             ^
rot.cpp: In function 'int main()':
rot.cpp:43:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
rot.cpp:44:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i < 2 * n; i++) scanf("%d", a + i);
                                                   ^

Subtask #1
0 / 9.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 21776 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 15268 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 10032 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 9520 KB Execution timed out
2 Halted 0 ms 0 KB -