QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#49252#2281. BnPCasdasdasfasdfasdfsdafWA 2ms3540kbC++3.2kb2022-09-19 20:32:102022-09-19 20:32:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-19 20:32:13]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3540kb
  • [2022-09-19 20:32:10]
  • 提交

answer

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cstring>
#include <functional>
#include <algorithm>


struct action
{
	uint64_t hash;
	int power;
	action( uint64_t n, int p )
	{
		hash = n; power = p;
	}
};

struct event_info
{
	uint64_t hash;
	uint32_t occurance;
	uint32_t power_required;
	uint32_t amount_at_max;
	event_info( uint64_t n_hash, uint32_t n_occurance, uint32_t n_power_required, uint32_t n_amount_at_max )
	{
		hash = n_hash;
		occurance = n_occurance;
		power_required = n_power_required;
		amount_at_max = n_amount_at_max;
	}
};

inline int calculate_score( std::vector<action> action_list, std::vector<event_info> event_list )
{
	int score = 0;
	for( const event_info& event_it : event_list ) {
		auto it = std::find_if( action_list.begin(), action_list.end(), [event_it]( action in_list ) {return  in_list.hash == event_it.hash; } );
		if( it != action_list.end() ) {
			score += it->power * ( event_it.occurance - event_it.amount_at_max );
		}
	}
	return score;
}

int main()
{
	std::ios_base::sync_with_stdio( false );
	std::cin.tie( NULL );
	int n, k;
	std::cin >> n; std::cin >> k;
	std::vector<action> action_list;
	action_list.reserve( n );
	char name[21];
	int power;
	for( int i = 0; i < n; i++ ) {

		std::cin >> name; std::cin >> power;
		action_list.emplace_back( std::hash<std::string>{}( name ), power );
	}

	int l;
	std::cin >> l;
	std::vector<event_info> event_list;
	event_list.reserve( l );

	for( int i = 0; i < l; i++ ) {
		std::cin >> name; std::cin >> power;
		uint64_t hash = std::hash<std::string>{}( name );
		auto it = std::find_if( event_list.begin(), event_list.end(), [hash]( event_info in_list ) {return  in_list.hash == hash; } );
		if( it != event_list.end() ) {
			it->occurance++;
			if( it->power_required == power ) {
				it->amount_at_max++;
			} else if( it->power_required < power ) {
				it->amount_at_max = 0;
				it->power_required = power;
			}
		} else {
			event_list.emplace_back( hash, 1, power, 1 );
		}
	}

	for( event_info& event_it : event_list ) {
		auto it = std::find_if( action_list.begin(), action_list.end(), [event_it]( action in_list ) {return in_list.hash == event_it.hash; } );
		if( it == action_list.end() ) {
			std::cout << 0 << "\n";
			return 0;
		} else if( event_it.power_required > it->power ) {
			int delta = event_it.power_required - it->power;
			it->power += delta;
			k -= delta;
		}
	}
	if( k < 0 ) {
		std::cout << 0 << "\n";
		return 0;
	}

	while( k ) {
		uint64_t target_hash = 0;
		event_info* target_einfo = nullptr;
		int best_improvement = 0;
		for( event_info& event_it : event_list ) {
			int improvement = event_it.occurance + ( event_it.amount_at_max * event_it.power_required );
			if( improvement > best_improvement ) {
				best_improvement = improvement;
				target_hash = event_it.hash;
				target_einfo = &event_it;
			}
		}
		auto it = std::find_if( action_list.begin(), action_list.end(), [target_hash]( action in_list ) {return in_list.hash == target_hash; } );
		it->power++;
		if( target_einfo ) {
			target_einfo->amount_at_max = 0;
		}
		k--;
	}

	std::cout << calculate_score(action_list, event_list) << "\n";

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3540kb

input:

3 14
THISISTHEONE 8
B 0
C 0
8
THISISTHEONE 10
C 0
B 1
B 0
THISISTHEONE 0
C 1
THISISTHEONE 0
THISISTHEONE 0

output:

83

result:

wrong answer 1st lines differ - expected: '82', found: '83'