12150 - Pole Position

[Kenpachi24]

In this problem, We have 3 variables

N= (2 ? N ? 10^3)
C= (1 ? C ? 10^4)
P= ( -10^6 ? P ? 10^6)

I think that the the variable P can not take values higher or lower outside the range of absolute value N. ----- P= ( -10^4 ? P ? 10^4)

[brianfry713]

If the value of P would cause that car to be outside the starting grid or two cars map to the same starting grid position then that test case is invalid and you should print -1.

[cse dipto]

Code: Select all

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <sstream>
#include <utility>
#define size 10000

using namespace std;

pair<long long int , long long int> p[size] ;
long long int grid[size] ;

int main()
{
    long long int i,j,k,t_case,car_no,pos,tmp,pos2,flag ;
    while(cin >> t_case)
    {
        memset(grid , 0 , sizeof(grid)) ;
        if(t_case == 0)
            break ;
        for(i = 0 ; i < t_case ; i++)
        {
            cin >> car_no >> pos ;
            p[i] = make_pair(car_no , pos) ;
        }
        for(i = 0 ; i < t_case ; i++)
        {
            flag = 1 ;
            pos2 = 0 ;
            tmp = p[i].second ;
            if(tmp > (t_case - 1))
            {
                //cout << p[i].first << " " ;
                flag = 0 ;
                printf("-1\n") ;
                break ;
            }
            else if(tmp < 0)
            {
                tmp = (tmp * (-1)) ;
                pos2 = i - tmp ;
                if(pos2 < 0)
                {
                    //cout << p[i].first << " " ;
                    flag = 0 ;
                    printf("-1\n") ;
                    break ;
                }
                if(grid[pos2] != 0)
                {
                    //cout << p[i].first << " " ;
                    flag = 0 ;
                    printf("-1\n") ;
                    break ;
                }
                if(grid[pos2] == 0)
                {
                    grid[pos2] = p[i].first ;
                }
            }
            else if(tmp > 0)
            {
                pos2 = i + tmp ;
                if(grid[pos2] != 0)
                {
                    //cout << p[i].first << " " ;
                    flag = 0 ;
                    printf("-1\n") ;
                    break ;
                }
                if(grid[pos2] == 0)
                {
                    grid[pos2] = p[i].first ;
                }
            }
            else if(tmp == 0)
            {
                if(grid[i] != 0)
                {
                    //cout << p[i].first << " " ;
                    flag = 0 ;
                    printf("-1\n") ;
                    break ;
                }
                if(grid[i] == 0)
                {
                    grid[i] = p[i].first ;
                }
            }
        }
        if(flag != 0)
        {
            for(i = 0 ; i < t_case ; i++)
            {
                cout << grid[i] ;
                if(i != (t_case -1))
                {
                    cout << " " ;
                }
            }
            cout << endl ;
        }
    }
    return 0;
}

[lbv]

code omitted

You may try these cases:

Input

Code: Select all

3
20 0
10 2
30 0
5
47 4
64 1
81 1
58 3
52 -4
0

Output

Code: Select all

-1
-1

[cse dipto]

@lbv thnks a lot bro got AC thnks again and you are great and also your's counter test cases thnks

[anacharsis]

I don't understand the second test case in the problem statement.

4
22 1
9 1
13 0
21 -2

The answer is given as -1 in the sample output.
But, isn't the following a valid starting grid for this case:
21 9 22 13

Any help appreciated!

[anacharsis]

Actually, never mind; I misunderstood the problem.
I thought that the car and position g/l information had been garbled.
It's not - the input is the current pole.
You just have to reconstruct the starting grid, which is a much easier problem than I tried to solve...