I’m trying to solve the PERMSUFF problem. The provided test cases and the other ones I’ve created all work perfectly fine. I’ve even created test problems to the upper bound of 100000 for both N and M. The only way I can get my code to throw an exception when running on my machine is by giving input that is outside of the constraints of the problem. Is this something I need to check for, or should I be able to assume the input is always within the constraints?
I’ve checked thing after thing and I still always get an NZEC when submitting through the problem.
Any help would be very appreciated. Here’s my code:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int[][] permArray;
static int[][] permPairs;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(in.readLine());
for(int tests=0; tests < T; tests++)
{
String[] line = in.readLine().split(" ");
int N = Integer.parseInt(line[0]);
int M = Integer.parseInt(line[1]);
permArray = new int[3][N];
permPairs = new int[2][M];
line = in.readLine().split(" ");
for(int i=0; i < line.length; i++)
{
permArray[0][i] = Integer.parseInt(line[i]);
permArray[1][i] = i;
permArray[2][i] = -(i+1);
}
for(int i=0; i < M; i++)
{
line = in.readLine().split(" ");
permPairs[0][i] = Integer.parseInt(line[0]);
permPairs[1][i] = Integer.parseInt(line[1]);
}
sort(0, N-1, permArray);
sort(0, M-1, permPairs);
int[][] groupedPairs = groupPairs(permPairs);
int count = 0;
for(int i=0; i < groupedPairs[0].length; i++)
{
count++;
for(int j = groupedPairs[0][i]-1; j < groupedPairs[1][i]; j++)
{
permArray[2][j] = count;
}
}
boolean possible = true;
for(int i=0; i < permArray[0].length; i++)
{
if(!(permArray[2][i]==permArray[2][permArray[1][i]]))
{
possible = false;
break;
}
}
System.out.println((possible)?"Possible":"Impossible");
}
}
private static int[][] groupPairs(int[][] array)
{
int j = 0;
int[][] groupedPairsTemp = new int[2][array[0].length];
groupedPairsTemp[0][0] = array[0][0];
groupedPairsTemp[1][0] = array[1][0];
for(int i=1; i < array[0].length; i++)
{
if(array[0][i]==array[1][i])//ignore pointless ranges
{
}
else if(array[0][i] <= groupedPairsTemp[1][j]) //still within range
{
groupedPairsTemp[1][j] = Math.max(array[1][i], groupedPairsTemp[1][j]);
}
else //need to create a new range;
{
j++;
groupedPairsTemp[0][j] = array[0][i];
groupedPairsTemp[1][j] = array[1][i];
}
}
int[][] groupedPairs = new int[2][j+1];
for(int i=0; i < j+1; i++)
{
groupedPairs[0][i] = groupedPairsTemp[0][i];
groupedPairs[1][i] = groupedPairsTemp[1][i];
}
return groupedPairs;
}
private static void sort(int low, int hi, int[][] array)
{
if(hi <= low)
return;
int j = hi+1;
int i = low;
double v = array[0][low];
while(true)
{
while(array[0][++i]<v)
if(i==hi)
break;
while(array[0][--j]>v)
if(j==low)
break;
if(i>=j)
break;
swap(i, j, array);
}
swap(low, j, array);
sort(low, j-1, array);
sort(j+1, hi, array);
}
private static void swap(int i, int j, int[][] array)
{
for(int k=0; k < array.length; k++)
{
int hold = array[k][i];
array[k][i] = array[k][j];
array[k][j] = hold;
}
}
}
Thanks!