3 svar
66 visningar
emilg 355
Postad: 12 nov 2020

Film critics

Var med i NCPC i lördags och även om det gick bra så lyckades vi inte lösa Film Critics (https://ncpc20.kattis.com/problems/filmcritics). Har inte tittat på koden direkt efter tävlingen och det var lite stressigt på slutet men om någon orkar sätta sin in i koden och se vad som blir fel så får ni gärna göra det. Men om jag ska vara ärlig, är det här mest för att testa den nya "Infoga programmeringskod" :)

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>


using namespace std;

int main () {
	int n,m,k;
	cin >> n;
	cin >> m;
	cin >> k;
	multiset<int> low;
	multiset<int> high;
	vector<int> list;
	map<int,vector<int>> my_map;
	int a;
	for(int i=0;i<n;i++) {
		cin >> a;
		list.push_back(a);

		if(my_map.find(a) == my_map.end() ) {
			my_map[a] = vector<int>();
		}
		my_map[a].push_back(i+1);

	}
	sort(list.begin(), list.end());

	if(k % m != 0) {
		cout << "impossible" << endl;
		return 0;

	}

	int number_m = k / m;

	//EXTRA
	if(number_m == n) {
		for(int i=0;i<n;i++)
			if(list[i] < m) {
				cout << "impossible" << endl;
				return 0;
			}
		for(int i=0;i<n;i++)
			cout << i+1 << ' ';
		return 0;
	}

	int count = 0;
	for(int i=n-1;i>=0;i--) {
		if(count < number_m)
			high.insert(list[i]);
		else
			low.insert(list[i]);
		count++;
	}

	int curr_up = m;
	int curr_down = 1;

	vector<int> order;
	multiset<int>::iterator itlow, ithigh;
	itlow = high.lower_bound(0);
	order.push_back( my_map[*itlow][ my_map[*itlow].size()-1] );
	my_map[*itlow].pop_back();

	for(int i=0;i<n-1;i++) {
		if(curr_down * k > curr_up * n) { //current average is too low => USE HIGH 
			// cout << "using high" << endl;
			itlow = high.lower_bound( int(ceil( (double)curr_up / (double)curr_down ) ) ); 
			if(itlow == high.end()) {
				cout << "impossible" << endl;
				return 0;
			}
			curr_up += m;
			curr_down += 1;
			order.push_back( my_map[*itlow][ my_map[*itlow].size()-1] );
			my_map[*itlow].pop_back();
			high.erase( itlow );
		}
		else { //current average is too high => USE LOW
			ithigh = low.upper_bound( int(floor( (double)curr_up / (double)curr_down ) ) );
			
			if(ithigh == low.begin()) {
				cout << "impossible" << endl;
				return 0;	
			}

			ithigh--;
			
			// curr_up += 0
			curr_down += 1;
			order.push_back( my_map[*ithigh][ my_map[*ithigh].size()-1] );
			my_map[*ithigh].pop_back();
			low.erase( ithigh);
		}
	}

	for(auto it=order.begin();it!=order.end();it++)
		cout << *it << ' ';

}
emilg 355
Postad: 12 nov 2020

Ser ju snyggt ut! Bra jobbat 👏

nigus 1
Postad: 3 dagar sedan

Vad kul att Film Critics har en egen pluggakutentråd :).

Jag tror att stycket under "EXTRA" kommer ge fel svar om alla tal utom ett är = M. Du har även glömt ett 'high.erase(itlow)' innan huvudloopen.

Intressant approach annars att kolla på nuvarande medelvärdet och girigt gå mot det sökta värdet, fick du det att funka till slut?
Känns som att det borde gå att få igenom det, men det finns fall när t.ex. alla a_i är samma och medelvärdet går "åt fel håll" trots att svaret blir rätt i slutändan:

5 6 18

4 4 4 4 4

Angående den infogade programmeringskoden tycker jag den ser snygg ut men det är ganska irriterande att den inte visar radnummer.

emilg 355
Postad: 3 dagar sedan

Har för mig att "EXTRA" var en riktig panikåtgärd haha. 

Jag tror väl egentligen snarare felaktig approach än intressant approach. Provade lite till med koden men fick inte det att funka så jag löste den genom att dela upp i två grupper och bara ta dem i stigande/sjunkade ordning (som de sa i lösningen tror jag). 

Just det, radnummer behövs ju. Finns plugin https://prismjs.com/plugins/line-numbers/. Ska fråga om det.

Svara Avbryt
Close