oj.uz

Submission #59836

# Submission time Handle Problem Language Result Execution time Memory
59836 2018-07-23T07:50:04 Z model_code Ranklist Sorting (BOI07_sorting) C++
40 / 100
 1000 ms 568 KB 
// Alexander Hullmann
// N^2 * 2^N implementation
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int N;
 
int best = -1;
int pos[1000];
int scores[1000];
int result[1000][2];
int history[1000][2];
int players_sorted[1000];
 
void move(int from, int to, int playernr)
{
	if (from > to)
	{
		for (int i = 0; i < N; i++)
			if (pos[i] >= to && pos[i] < from)
				pos[i]++;
		pos[playernr] = to;
	}
	else if (from < to)
	{
		for (int i = 0; i < N; i++)
			if (pos[i] > from && pos[i] <= to)
				pos[i]--;
		pos[playernr] = to;
	}
	
}
 
int rek(int player, int costs)
{
	if (player == N)
	{
		if (best == -1 || best > costs)
		{
			best = costs;
			for (int i = 0; i < N; i++)
			{
				result[i][0] = history[i][0];
				result[i][1] = history[i][1];
			}
		}
		return 0;
	}
	
	int result = -1;
	
	if (player == 0 || pos[players_sorted[player - 1]] > pos[players_sorted[player]])
	{
		history[player][0] = -1;
		result = rek(player + 1, costs);
	}
	int to;
	
	int from = pos[players_sorted[player]];
	
	if (player)
	{
		to = pos[players_sorted[player - 1]];
		if (from < to) to--;
	}
	else
		to = N - 1;
	
	move(from, to, players_sorted[player]);
	history[player][0] = from; history[player][1] = to;
	int rv = rek(player + 1, costs + to + from + 2) + to + from + 2;
	move(to, from, players_sorted[player]);
	
	if (result == -1 || rv < result)
		result = rv;
	
	return result;
}
 
 
int comparescores(const void* a, const void* b)
{
	return (scores[*(int *)a] - scores[*(int *)b]);
}
 
int main()
{
	FILE* in = stdin;
	fscanf(in, "%d ", &N);
	for (int i = 0; i < N; i++)
	{
		fscanf(in, "%d ", &scores[i]);
		pos[i] = i;
		players_sorted[i] = i;
	}
	fclose(in);
	
	qsort(players_sorted, N, sizeof(int), comparescores);
	
	rek(0, 0);
	
	int movecount = 0;
	
	for (int i = 0; i < N; i++)
		if (result[i][0] != -1)
			movecount++;
	
	FILE* out = stdout;
	fprintf(out, "%d\n", movecount);
	for (int i = 0; i < N; i++)
		if (result[i][0] != -1)
			fprintf(out, "%d %d\n", result[i][0] + 1, result[i][1] + 1);
	fclose(out);		
	
	return 0;
}

Compilation message

sorting.cpp: In function 'int main()':
sorting.cpp:91:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(in, "%d ", &N);
  ~~~~~~^~~~~~~~~~~~~~~
sorting.cpp:94:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(in, "%d ", &scores[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 196 ms 484 KB Output is correct
5 Execution timed out 1078 ms 544 KB Time limit exceeded
6 Execution timed out 1075 ms 544 KB Time limit exceeded
7 Execution timed out 1101 ms 544 KB Time limit exceeded
8 Execution timed out 1083 ms 544 KB Time limit exceeded
9 Execution timed out 1090 ms 568 KB Time limit exceeded
10 Execution timed out 1077 ms 568 KB Time limit exceeded