But why its 1 instead of 0 or 2 on this test case:
Code: Select all
4
0 0
0 1
1 1
1 0
6
3 2
3 1
2 1
1 1
1 2
2 2
brianfry713 wrote:My AC output for the input you posted is:Code: Select all
2 1 1
Moderator: Board moderators
Code: Select all
4
0 0
0 1
1 1
1 0
6
3 2
3 1
2 1
1 1
1 2
2 2
brianfry713 wrote:My AC output for the input you posted is:Code: Select all
2 1 1
thank you very much! Ill try with this ...brianfry713 wrote:Your input is not valid. The malls do not intersect, even in one point. I tested the judge's input.
Code: Select all
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.HashSet;
import java.util.Collection;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
* @author Andrew Shmig aka SyFyKid
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
MallMania solver = new MallMania();
solver.solve(1, in, out);
out.close();
}
}
class MallMania {
public void solve(int testNumber, InputReader in, PrintWriter out) {
final int MAX_SIZE = 2001;
final int PRIME = 1997;
int[] DX = {-1, 0, +1, 0}, DY = {0, -1, 0, +1};
int p1;
Queue<Integer> q = new LinkedList<Integer>();
HashSet<Integer> used = new HashSet<Integer>();
while((p1 = in.RI())!=0){
// mall 1
for(int i=0; i<p1; i++){
int x = Integer.parseInt(in.RS()), y = Integer.parseInt(in.RS());
int tmp = (x*PRIME + y)*PRIME;
q.add(tmp);
used.add(tmp);
}
// mall 2
int p2 = in.RI();
for(int i=0; i<p2; i++){
int x = Integer.parseInt(in.RS()), y = Integer.parseInt(in.RS());
int tmp = (x*PRIME + y)*PRIME;
used.add(-tmp);
}
// bfsing
exit:
while(!q.isEmpty()) {
int cur = q.poll();
int curX = cur/PRIME/PRIME, curY = cur/PRIME%PRIME, curD = cur%PRIME;
for(int i=0; i<DX.length; i++){
Integer newX = curX + DX[i], newY = curY + DY[i], newD = curD + 1, tmp = (newX*PRIME + newY)*PRIME + newD;
if(newX>=0 && newX<MAX_SIZE && newY>=0 && newY<MAX_SIZE){
if(used.contains(-(tmp - tmp%PRIME))){
out.println(tmp%PRIME + 1);
break exit;
}
if(!used.contains(tmp)){
q.add(tmp);
used.add(tmp);
}
}
}
}
// init
q = new LinkedList<Integer>();
used = new HashSet<Integer>();
}
}
}
class InputReader {
private BufferedReader reader;
private StringTokenizer tokenizer;
public InputReader(InputStream stream)
{
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next()
{
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public String RS()
{
return next();
}
public int RI()
{
return Integer.parseInt(next());
}
}
brianfry713 wrote:Why are you using 1997?
brianfry713 wrote:My C++ code that got AC in 0.752 sec I rewrote in JAVA and got TLE.
brianfry713 wrote:I optimized my JAVA code and got AC in 1.084 sec. I used BufferedReader and BufferedWriter. A faster way to combine two integers is to use shift and bitwise and. I kept the distance in it's own 2-D array and placed x and y into the queue.
To add to the queue:
Q[tail++]=(x<<11)+y;
To remove from the queue:
x=Q[head]>>11;
y=Q[head++]&2047;
I also changed from a standard flood fill to a bidirectional meet in the middle approach, but didn't see much difference in the runtime.
Code: Select all
import java.util.BitSet;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
* @author Andrew Shmig aka SyFyKid
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
MallMania solver = new MallMania();
solver.solve(1, in, out);
out.close();
}
}
class MallMania {
int[] q = new int[4008004];
int[][] data = new int[2009][2009];
int[] DX = {-1, 0, +1, 0}, DY = {0, -1, 0, +1};
BitSet used = new BitSet(4006008), used2 = new BitSet(4006008);
public void solve(int testNumber, InputReader in, PrintWriter out) {
int p1, p2;
int left, right;
int MAX_SIZE = 2001;
while(true){
left = right = 0;
p1 = in.RI();
if(p1 == 0) break;
for(int i=0; i<p1; i++){
int x = in.RI(), y = in.RI();
q[right++] = (x<<11) + y;
used.set(x*MAX_SIZE + y);
data[x][y] = 0;
}
p2 = in.RI();
for(int i=0; i<p2; i++){
int x = in.RI(), y = in.RI();
used2.set(x*MAX_SIZE + y);
}
exit:
while(true){
int cell = q[left++];
int curX = (cell>>11), curY = (cell&2047);
for(int i=0; i<DX.length; i++){
int newX = curX + DX[i], newY = curY + DY[i];
if(newX>=0 && newX<=MAX_SIZE && newY>=0 && newY<=MAX_SIZE){
if(used2.get(newX*MAX_SIZE + newY)){
out.println(data[curX][curY] + 1);
break exit;
}
if(!used.get(newX*MAX_SIZE + newY)){
q[right++] = (newX<<11) + newY;
data[newX][newY] = data[curX][curY] + 1;
used.set(newX*MAX_SIZE + newY);
}
}
}
}
// clearing
used.clear();
used2.clear();
}
}
}
class InputReader {
private BufferedReader reader;
private StringTokenizer tokenizer;
public InputReader(InputStream stream)
{
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next()
{
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int RI()
{
return Integer.parseInt(next());
}
}
brianfry713 wrote:I optimized my JAVA code and got AC in 1.084 sec. I used BufferedReader and BufferedWriter. A faster way to combine two integers is to use shift and bitwise and. I kept the distance in it's own 2-D array and placed x and y into the queue.
To add to the queue:
Q[tail++]=(x<<11)+y;
To remove from the queue:
x=Q[head]>>11;
y=Q[head++]&2047;
I also changed from a standard flood fill to a bidirectional meet in the middle approach, but didn't see much difference in the runtime.