oj.uz

Submission #703204

# Submission time Handle Problem Language Result Execution time Memory
703204 2023-02-26T14:34:38 Z Doncho_Bonboncho Arranging Shoes (IOI19_shoes) C++14
10 / 100
 29 ms 5428 KB 
#include <bits/stdc++.h>
#include "shoes.h"

typedef long long ll;

const int MAX_N = 1e6 + 42;

int p[MAX_N];
int last[MAX_N];

int tree[MAX_N];

void add( int x, int v ){
//	std::cerr<<" ! "<<x<<"\n";
	while( x < MAX_N ){
		tree[x] += v;
		x += x&(-x);
	}
}

int query( int x ){
	int nas = 0;
	while( x ){
		nas += tree[x];
		x -= x&(-x);
	}
	return nas;
}

bool oke[MAX_N];
bool l[MAX_N];

long long count_swaps(std::vector<int> s) {

	ll nas = 0; 
	
	int n = s.size();
	for( int i=1 ; i<=n ; i++ ){
		if( s[i-1] < 0 ) l[i] = true;
		int curr = abs( s[i-1] );
	//	std::cerr<<" ! "<<curr<<"\n";
	//	std::cerr<<last[curr]<<"\n";
		if( last[curr] == 0 ) last[curr] = i;
		else{
			p[i] = last[curr];
			p[last[curr]] = i;

			last[curr] = 0;
 		}
		add( i, 1 );
	}

	/*
	for( int i=1 ; i<=n ; i++ )
		std::cerr<<p[i]<<" ";
	std::cerr<<"\n";
	*/

	for( int i=1 ; i<=n ; i++ ){
		while( i<=n and oke[i] ) i++;
		if( i > n ) break;

		ll currNas = query( p[i] )-1;
		if( l[i] ){
	//		std::cerr<<"l -> -1 \n";
			currNas --;
		}

	//	std::cerr<<" ! "<<i<<" "<<p[i]<<" -> "<<currNas<<"\n\n";
		nas += currNas;

		add( i, -1 );
		add( p[i], -1 );

		oke[i] = true;
		oke[p[i]] = true;
	}

	return nas;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 308 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 304 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 28 ms 5324 KB Output is correct
6 Incorrect 29 ms 5428 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 308 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 308 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -