Optimization in competitive programming - C++ - TLE problem

Asked

Viewed 44 times

1

I’m solving a question that asks us to print on the screen the winner id of each test round.

The game works as follows:

N cards are dealt to P players of a total of G cards.

The letter [G - N*P+1] will be dealt to the discard and the following cards will go to the draw (the order of the cards at the entrance is the order from the top to the base of the pile).

  1. Game goes clockwise
  2. There are two hills, one of discard and the other of plunder.
  3. In the player’s round, if he holds a card with the value or suit equivalent to the card at the top of the discard, he can discard the card (if several cards are candidates, the one with the highest value is discarded).
  4. If the player does not have candidate cards he will have to pick a card from the top of the draw.
  5. the player who discards all cards wins.

Note: Some cards have powers (uno style):

  • card 12(Queen): reverses the direction of the game. If it is the first card at the beginning of the game (the card starting at the discard), the first player P[0] will play normally but the next will be the anti time (P = 0,1,2,3; then anti time = 0,3,2,1,0...)
  • Card 7: The next player loses his turn and picks up two cards from the draw.
  • Card 1: Next player loses his turn and takes a draw card.
  • card 11: next player loses turn.

The original text of the question is in: https://neps.academy/problem/270

I solved with the following code:


#include <bits/stdc++.h>

#define ff first
#define ss second
#define pb push_back
#define PLAYERS 10

const char PAUS = 'C';
const char OUROS = 'D';
const char COPAS = 'H';
const char ESPADAS = 'S';

using namespace std;
using ia = pair<int, char>;

ia descarte;
vector<ia> mao[PLAYERS];
vector<ia> saque;
int players, pcards, gcards;
bool effect = false, sentido = true;

void verifyEffect(){
    if(descarte.ff == 1 || descarte.ff == 7 || descarte.ff == 11)
        effect = true;
    else if(descarte.ff == 12){
        sentido = !sentido;
    }
}
bool vePlayer(ia a, ia b){
    if(a.ff == descarte.ff || b.ff == descarte.ff){
        if(a.ff == b.ff){
            if(a.ss == ESPADAS || (a.ss == COPAS && b.ss != ESPADAS) || (a.ss == OUROS && b.ss == PAUS))
                return false;
        }else if(a.ff == descarte.ff) return false;
    }
    if(a.ss == descarte.ss || b.ss == descarte.ss){
        if(a.ss == b.ss && a.ff > b.ff) return false;  
        else if(a.ss == descarte.ss) return false;
    }
    return true;
}
int proxRound(int jogadorr = -1){ // jogador = atual != prox
    int jogador = jogadorr;
    int proxJogador;
    if(jogador == -1) jogador = 0;
    if(sentido){
        if(jogador+1 > players - 1) proxJogador = 0;
        else proxJogador = jogador + 1;
    }else{
        if(jogador-1 < 0) proxJogador = players - 1;
        else proxJogador = jogador - 1;
    }
    //printf("jogador: %d\n", jogador);
    if(effect){
        if(descarte.ff == 1){
            mao[jogador].pb(saque.back());
            saque.pop_back();
        }else if(descarte.ff == 7){
            mao[jogador].pb(saque.back());
            saque.pop_back();
            mao[jogador].pb(saque.back());
            saque.pop_back();
        }
        effect = false;  
    }else{
        sort(mao[jogador].begin(), mao[jogador].end(), vePlayer);
        if(mao[jogador].back().ss == descarte.ss || mao[jogador].back().ff == descarte.ff){
            descarte = mao[jogador].back();
            mao[jogador].pop_back();
            if(mao[jogador].size() == 0){
                return jogador + 1; 
            }
            verifyEffect();
        }else{
            mao[jogador].pb(saque.back());
            saque.pop_back();
        }
    }
    return proxRound(proxJogador);
}
int main(){

    while(true){
        //printf("entrou\n");
        scanf("%d %d %d", &players, &pcards, &gcards);
        effect = false;
        if(players == 0 && pcards == 0 && gcards == 0) break;
        for(int jogador = 0; jogador < players; jogador++){
            mao[jogador].clear();
            for(int cartas = 0; cartas < pcards; cartas++){
                pair<int,char> c;
                scanf("%d %c", &c.ff, &c.ss);
                mao[jogador].pb(c); // emplace_back(ff,ss)
            }
        }
        scanf("%d %c", &descarte.ff,&descarte.ss);
        verifyEffect();

        saque.clear();
        saque.reserve(gcards - players*pcards);
        for(int nsaque = gcards - players*pcards - 2; nsaque >= 0; nsaque--){
            pair<int,char> c;
            scanf("%d %c", &saque[nsaque].ff ,&saque[nsaque].ss);
        }
        printf("%d\n", proxRound());
    }
    return 0;
}

It returns the correct answer, but I get TLE (Time limit exceeded). How can I optimize this code?

The time limit is 1s.

  • The compiler should remove this tail recursion, but has tried removing yourself and swapping for a loop on proxRound? Luckily, you can see the "hotspots" using the kcachegrind, a tool of valgrind. Take a look here for your questions. Of course, use input redirect to avoid computing your interacting time. If you are on Windows, try a native tool, it seems that the valgrind doesn’t work as well at WSL

No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.