API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 4th, 2015
62
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 21.45 KB | None | 0 0
raw download clone embed print report
  1. /**
  2.  *  Task:    Civilization
  3.  *  Author:  Evgeniy Chetvertakov
  4.  *  Verdict: OK
  5.  *  Max flow solution with proper capacities on cities and "do not shoot" end vertices.
  6.  */
  7.  
  8. import java.io.FileInputStream;
  9. import java.io.FileNotFoundException;
  10. import java.io.PrintWriter;
  11. import java.util.ArrayList;
  12. import java.util.Collections;
  13. import java.util.Comparator;
  14. import java.util.HashMap;
  15. import java.util.LinkedList;
  16. import java.util.Queue;
  17. import java.util.Scanner;
  18. import java.util.TreeMap;
  19. import java.util.TreeSet;
  20.  
  21.  
  22. public class Task {
  23.  
  24.         abstract class GraphNode implements Comparable<GraphNode>{
  25.                 public boolean equals(Object o) { return compareTo((GraphNode)o) == 0; }
  26.                 public int compareTo(GraphNode o) {
  27.                         //return this.toString().compareTo(o.toString());
  28.                         int ta,tb;
  29.  
  30.                         if(this instanceof Point3D) ta=1;
  31.                         else if(this instanceof Point) ta=2;
  32.                         else if(this instanceof GraphNodeImpl) ta=3;
  33.                         else throw new Error("something wrong. HBWYGSBV");
  34.  
  35.                         if(o instanceof Point3D) tb=1;
  36.                         else if(o instanceof Point) tb=2;
  37.                         else if(o instanceof GraphNodeImpl) tb=3;
  38.                         else throw new Error("something wrong. RGTBEAVT");
  39.  
  40.                         if(ta != tb ) return Integer.compare(ta, tb);
  41.                         if(ta == 1) return ((Point3D)this).compareTo((Point3D)o);
  42.                         if(ta == 2) return ((Point)this).compareTo((Point)o);
  43.                         if(ta == 3) return ((GraphNodeImpl)this).compareTo((GraphNodeImpl)o);
  44.                         throw new Error("EBRHERY%B");
  45.  
  46.                 }
  47.                 public int hashCode() { throw new Error("hashCode is not implemented here"); }
  48.         };
  49.  
  50.         class GraphNodeImpl extends GraphNode {
  51.                 private String name;
  52.                 public GraphNodeImpl(String name) {this.name = name;}
  53.                 public String toString() { return name; }
  54.                 public int hashCode() { return name.hashCode(); }
  55.                 public int compareTo(GraphNodeImpl o) { return name.compareTo(o.name); }
  56.         };
  57.  
  58.         class Point extends GraphNode{
  59.                 public int x,y; //immutable
  60.                 private String strrepr=null;
  61.                 public Point(int x,int y) { this.x = x; this.y=y; }
  62.                 public Point(Point p) { this.x = p.x; this.y=p.y; }
  63.                 public Point add(Point p) { return new Point(this.x+p.x,this.y+p.y); }
  64.                 public String toString() {
  65.                         if(strrepr==null) strrepr=String.format("(%d,%d)", x,y);
  66.                         return strrepr;
  67.                 }
  68.                 public int hashCode() { return (x<<10)^(y<<5)^y^x; }
  69.                 public int compareTo(Point o) {
  70.                         if( this.x == o.x )  return Integer.compare(this.y, o.y);
  71.                         return Integer.compare(this.x, o.x);
  72.                 }
  73.         }
  74.  
  75.         class Point3D extends Point {
  76.                 private int z;
  77.                 private String strrepr=null;
  78.                 public Point3D(Point p,int z) { super(p); this.z=z;}
  79.                 public String toString() {
  80.                         if(strrepr==null) strrepr=String.format("(%d,%d,%d)", x,y,z);
  81.                         return strrepr;
  82.                 }
  83.                 public int hashCode() { return (x<<10)^(y<<6)^(z<<3)^y^x^z; }
  84.                 public int compareTo(Point3D o) {
  85.                         if( this.z == o.z )
  86.                         {
  87.                                 if( this.x == o.x )  return Integer.compare(this.y, o.y);
  88.                                 return Integer.compare(this.x, o.x);
  89.                         }
  90.                         return Integer.compare(this.z, o.z);
  91.                 }
  92.  
  93.         }
  94.  
  95.  
  96.         class UnpassableCell extends Point { protected UnpassableCell(int x,int y) { super(x,y); } };
  97.  
  98.         class City extends UnpassableCell {
  99.                 public int n,health;
  100.                 public City(int x,int y,int n,int health) { super(x, y); this.n=n; this.health=health; }
  101.         }
  102.  
  103.         class Mountain extends UnpassableCell {
  104.                 public int n,health;
  105.                 public Mountain(int x,int y) { super(x, y); }
  106.         }
  107.  
  108.         class Catapult extends Point {
  109.                 public int n,movesCount;
  110.                 public Catapult(int x,int y,int n,int movesCount) { super(x, y); this.n=n; this.movesCount=movesCount; }
  111.         }
  112.  
  113.  
  114.         // arcs
  115.         abstract class Arc implements Comparable<Arc>{
  116.                 abstract public GraphNode getFrom();
  117.                 abstract public GraphNode getTo();
  118.                 abstract public int getVolume();
  119.                 abstract public int getWeight();
  120.                 abstract public Arc getBackArc();
  121.                 abstract public void addWeight(int d);
  122.                 public String toString() { return getFrom().toString() + " -> " + getTo().toString(); }
  123.                 public int compareTo(Arc o) {
  124.                         //return this.toString().compareTo(o.toString());
  125.                         int a = this.getFrom().compareTo(o.getFrom());
  126.                         if( a != 0 ) return a;
  127.                         return this.getTo().compareTo(o.getTo());
  128.                 }
  129.         }
  130.  
  131.         class DirectArc extends Arc {
  132.                 private GraphNode from,to;
  133.                 private int volume,weight;
  134.                 private BackArc back = null;
  135.                 public DirectArc(GraphNode from,GraphNode to, int volume, int weight)
  136.                 {
  137.                         this.from = from;
  138.                         this.to = to;
  139.                         this.volume = volume;
  140.                         this.weight = weight;
  141.                 }
  142.                 public Arc getBackArc()
  143.                 {
  144.                         if( back == null ) back = new BackArc(this);
  145.                         return back;
  146.                 }
  147.  
  148.                 public GraphNode getFrom() { return from; }
  149.                 public GraphNode getTo() { return to; }
  150.                 public int getVolume() { return volume;        }
  151.                 public int getWeight() { return weight;        }
  152.                 public void addWeight(int d) { weight+=d; }
  153.         }
  154.         class BackArc extends Arc {
  155.                 private DirectArc directArc;
  156.                 public BackArc(DirectArc arc) { directArc = arc; }
  157.                 public GraphNode getFrom() { return directArc.getTo(); }
  158.                 public GraphNode getTo() { return directArc.getFrom(); }
  159.                 public int getVolume() { return directArc.getVolume();        }
  160.                 public int getWeight() { return directArc.getVolume() - directArc.getWeight(); }
  161.                 public void addWeight(int d) { directArc.addWeight(-d); }
  162.                 public Arc getBackArc() {        return directArc; }
  163.         }
  164.  
  165.         public class Tuple<A, B> {
  166.                   public final A first;
  167.                   public final B second;
  168.                   public Tuple(A first, B second) {
  169.                     this.first = first;
  170.                     this.second = second;
  171.                   }
  172.                 }
  173.  
  174.         class Graph
  175.         {
  176.                 public TreeSet<Arc> arcs;
  177.                 public TreeMap<GraphNode,ArrayList<Arc> > nodesFrom;
  178.                 public Graph(TreeSet<Arc> arcs) {
  179.                         this.arcs = arcs;
  180.  
  181.                         nodesFrom = new TreeMap<GraphNode,ArrayList<Arc> >();
  182.                         for(Arc arc : arcs) {
  183.                                 if( !nodesFrom.containsKey(arc.getFrom()) ) nodesFrom.put(arc.getFrom(), new ArrayList<Arc>());
  184.                                 nodesFrom.get(arc.getFrom()).add(arc);
  185.                         }
  186.                         for(Arc arc : arcs) {
  187.                                 Arc ba = arc.getBackArc();
  188.                                 if( !nodesFrom.containsKey(ba.getFrom()) ) nodesFrom.put(ba.getFrom(), new ArrayList<Arc>());
  189.                                 nodesFrom.get(ba.getFrom()).add(ba);
  190.                         }
  191.                 }
  192.  
  193.                 public TreeSet<Arc> getDirectEmpties(GraphNode node) {
  194.                         TreeSet<Arc> res = new TreeSet<Arc>();
  195.                         for( Arc a : nodesFrom.get(node) )
  196.                         {
  197.                                 if( (a instanceof DirectArc) && a.getWeight() == 0 )
  198.                                         res.add(a);
  199.                         }
  200.                         return res;
  201.                 }
  202.  
  203.                 public Arc getDirectEmpty(GraphNode node) {
  204.                         for( Arc a : nodesFrom.get(node) )
  205.                                 if( (a instanceof DirectArc) && a.getWeight() == 0 )
  206.                                         return a;
  207.                         return null;
  208.                 }
  209.  
  210.  
  211.                 public TreeSet<Arc> findPath(GraphNode from,GraphNode to)
  212.                 {
  213.                         HashMap<GraphNode,Arc> visited = new HashMap<>(nodesFrom.size()*2,0.5f);
  214.                         visited.put(from, null);
  215.                         Queue<GraphNode> queue = new LinkedList<>();
  216.                         queue.add(from);
  217.  
  218.                         while(!queue.isEmpty())
  219.                         {
  220.                                 GraphNode node = queue.remove();
  221.                                 for( Arc arc : nodesFrom.get(node) )
  222.                                 {
  223.                                         if( visited.containsKey(arc.getTo())) continue;
  224.                                         if( arc.getWeight() < 1) continue;
  225.                                         visited.put(arc.getTo(),arc);
  226.                                         if(arc.getTo().equals(to)) { queue.clear(); break;}
  227.                                         queue.add(arc.getTo());
  228.                                 }
  229.                         }
  230.  
  231.                         if(! visited.containsKey(to)) return null;
  232.  
  233.                         TreeSet<Arc> res = new TreeSet<>();
  234.                         GraphNode node = to;
  235.                         do {
  236.                                 Arc a = visited.get(node);
  237.                                 res.add(a);
  238.                                 node = a.getFrom();
  239.                         } while( !node.equals(from));
  240.  
  241.                         return res;
  242.                 }
  243.         }
  244.  
  245.         interface Field {
  246.                 boolean checkCell(Point p);
  247.         };
  248.  
  249.  
  250.         // distances from the given point to neighborhood cells
  251.         ArrayList<Point> moves = new ArrayList<Point>();
  252.         {
  253.                 moves.add(new Point(0,1));
  254.                 moves.add(new Point(1,0));
  255.                 moves.add(new Point(1,-1));
  256.                 moves.add(new Point(0,-1));
  257.                 moves.add(new Point(-1,0));
  258.                 moves.add(new Point(-1,1));
  259.         }
  260.  
  261.  
  262.         TreeMap<Integer, TreeSet<Point> > walk(int depth, Point startFrom, Field f )
  263.         {
  264.                 if( depth == 0 ) {
  265.                         TreeMap<Integer, TreeSet<Point> > res = new TreeMap<Integer, TreeSet<Point> >();
  266.                         TreeSet<Point> setp = new TreeSet<Point>();
  267.                         setp.add(startFrom);
  268.                         res.put(0,setp);
  269.                         return res;
  270.                 }
  271.  
  272.                 TreeMap<Integer, TreeSet<Point> > distances = walk(depth-1,startFrom,f);
  273.                 TreeSet<Point> d1 = distances.get(depth-1);
  274.                 TreeSet<Point> d2 = distances.containsKey(depth-2)?distances.get(depth-1):new TreeSet<Point>();
  275.  
  276.                 TreeSet<Point> w =  new TreeSet<Point>();
  277.                 for(Point p : d1)
  278.                         for(Point move : moves)
  279.                         {
  280.                                 Point n = p.add(move);
  281.                                 if( !d1.contains(n) || !d2.contains(n)) w.add(n);
  282.                         }
  283.  
  284.                 TreeSet<Point> res =  new TreeSet<Point>();
  285.                 for(Point p : w)
  286.                         if( f.checkCell(p)) res.add(p);
  287.  
  288.                 distances.put(depth, res);
  289.                 return distances;
  290.         }
  291.  
  292.         TreeMap<Catapult , Tuple<Point,City> > calc(Field moves_field, Field firing_field, ArrayList<City> cities, ArrayList<Catapult> cats)
  293.         {
  294.                 GraphNode source = new GraphNodeImpl("source");
  295.                 GraphNode sink = new GraphNodeImpl("sink");
  296.  
  297.                 TreeMap<City, TreeSet<Point> > city_area = new TreeMap<>();
  298.                 for(City city : cities)
  299.                 {
  300.                         TreeMap<Integer, TreeSet<Point> > areas = walk(2,city,firing_field);
  301.                         TreeSet<Point> area = new TreeSet<>();
  302.                         for( TreeSet<Point> area_p : areas.values()) {
  303.                                 area.addAll(area_p);
  304.                         }
  305.                         city_area.put(city, area);
  306.                 }
  307.  
  308.  
  309.                 TreeMap<Catapult, TreeSet<Point> > cat_area = new TreeMap<>();
  310.                 for(Catapult cat : cats)
  311.                 {
  312.                         TreeMap<Integer, TreeSet<Point> > areas = walk(cat.movesCount-1,cat,moves_field);
  313.                         TreeSet<Point> area = new TreeSet<>();
  314.                         for( TreeSet<Point> area_p : areas.values()) {
  315.                                 area.addAll(area_p);
  316.                         }
  317.                         cat_area.put(cat, area);
  318.                 }
  319.  
  320.                 TreeSet<Arc> arcs = new TreeSet<>();
  321.  
  322.                 TreeMap<Catapult , Tuple<Point,City> > res = new TreeMap<>();
  323.                 int unused_catpower = cats.size();
  324.                 for(City city : cities)
  325.                         unused_catpower -= city.health;
  326.                 if( unused_catpower < 0) return res;
  327.                 cities = new ArrayList<>(cities);
  328.                 cities.add( new City(-1,-1,0,unused_catpower) );
  329.  
  330.                 for(Catapult cat : cats)
  331.                         arcs.add(new DirectArc(source,cat,1,1));
  332.  
  333.                 for(Catapult cat : cats)
  334.                 {
  335.                         TreeSet<Point> cat_set = cat_area.get(cat);
  336.                         for(City city : cities)
  337.                         {
  338.                                 TreeSet<Point> intersection = new TreeSet<Point>();
  339.                                 if( city.n > 0)
  340.                                 {
  341.                                         for(Point p : city_area.get(city))
  342.                                                 if(cat_set.contains(p)) intersection.add(p);
  343.                                 }else{
  344.                                         intersection.add(cat);
  345.                                 }
  346.  
  347.                                 for(Point p : intersection)
  348.                                 {
  349.                                         Point cell1 = new Point3D(p,1);
  350.                                         Point cell2 = new Point3D(p,2);
  351.  
  352.                                         arcs.add(new DirectArc(cat,cell1,1,1));
  353.                                         arcs.add(new DirectArc(cell1,cell2,1,1));
  354.                                         arcs.add(new DirectArc(cell2,city,1,1));
  355.  
  356.                                 }
  357.                         }
  358.                 }
  359.  
  360.  
  361.                 for(City city : cities)
  362.                         arcs.add(new DirectArc(city,sink,city.health,city.health));
  363.  
  364.                 Graph g = new Graph(arcs);
  365.  
  366.                 while(true) {
  367.                         TreeSet<Arc> path = g.findPath(source,sink);
  368.                         if( path == null) break;
  369.                         for(Arc a : path) a.addWeight(-1);
  370.                 }
  371.  
  372.                 boolean flag = true;
  373.                 for(Arc arc : g.nodesFrom.get(sink) )
  374.                         if(arc.getBackArc().getWeight() != 0)
  375.                                 flag=false;
  376.  
  377.  
  378.                 if(!flag) return res; // no solution for this set of cities
  379.  
  380.                 for(Arc catarc : g.getDirectEmpties(source)) {//g.nodesFrom.get(source)) {
  381.                          //if( catarc.getWeight() != 0) continue;
  382.                          Catapult cat = (Catapult)catarc.getTo();
  383.  
  384.                          Arc cell1arc = g.getDirectEmpty(cat);
  385.                          Point cell1 = (Point)cell1arc.getTo();
  386.                          Arc cell2arc = g.getDirectEmpty(cell1);
  387.                          Arc cityarc = g.getDirectEmpty(cell2arc.getTo());
  388.                          City city = (City)cityarc.getTo();
  389.  
  390.                          res.put(cat, new Tuple<Point,City>(cell1,city));
  391.                 }
  392.                 return res;
  393.  
  394.         }
  395.  
  396.         public void task(String inputfile,String outputfile)
  397.         {
  398.                 try{
  399.                         Scanner inp = new Scanner( new FileInputStream(inputfile) );
  400.  
  401.                         final int W = inp.nextInt();
  402.                         final int H = inp.nextInt();
  403.  
  404.                         int N = inp.nextInt();
  405.                         ArrayList<City> cities = new ArrayList<City>();
  406.                         for(int i=1;i<=N;i++)
  407.                                 cities.add( new City(inp.nextInt(),inp.nextInt(),i,inp.nextInt()) );
  408.  
  409.                         int C = inp.nextInt();
  410.                         ArrayList<Catapult> cats = new ArrayList<Catapult>();
  411.                         for(int i=1;i<=C;i++)
  412.                                 cats.add( new Catapult(inp.nextInt(),inp.nextInt(),i,inp.nextInt()) );
  413.  
  414.                         int M = inp.nextInt();
  415.                         ArrayList<Mountain> mountains = new ArrayList<Mountain>();
  416.                         for(int i=1;i<=M;i++)
  417.                                 mountains.add( new Mountain(inp.nextInt(),inp.nextInt()) );
  418.  
  419.                         inp.close();
  420.  
  421.                         // subsets of cities
  422.                         ArrayList< ArrayList<City> > aac = new ArrayList< ArrayList<City> >();
  423.                         for(int i=(1<<N)-1;i>0;i--)
  424.                         {
  425.                                 ArrayList<City> a = new ArrayList<City>(cities);
  426.                                 for(int j=N-1;j>=0;j--)
  427.                                         if( (i & (1<<j)) == 0) a.remove(j);
  428.                                 aac.add(a);
  429.                         }
  430.  
  431.                         Collections.sort(aac,
  432.                         //aac.sort(
  433.                                         new Comparator< ArrayList<City> >() {
  434.                                 public int compare(ArrayList<City> a, ArrayList<City> b) {
  435.                                         return b.size() - a.size();
  436.                                 }
  437.                         });
  438.  
  439.                         // field's configuration
  440.                         final TreeSet<UnpassableCell> unpassables = new TreeSet<UnpassableCell>();
  441.                         for(City c : cities) unpassables.add(c);
  442.                         for(Mountain m : mountains) unpassables.add(m);
  443.  
  444.                         Field moves_field = new Field() {
  445.                                 public boolean checkCell(Point p) {
  446.                                         return p.x>=0 && p.x<W && p.y>=0 && p.y<H && !unpassables.contains(p);
  447.                                 }
  448.                         };
  449.                         Field firing_field = new Field() {
  450.                                 public boolean checkCell(Point p) {
  451.                                         return p.x>=0 && p.x<W && p.y>=0 && p.y<H;
  452.                                 }
  453.                         };
  454.  
  455.  
  456.                         TreeMap<Catapult , Tuple<Point,City> > sol=null;
  457.                         int cityres=0;
  458.                         for(ArrayList<City> cities_subset : aac)
  459.                         {
  460.                                 sol = calc(moves_field,firing_field,cities_subset,cats);
  461.                                 if( ! sol.isEmpty() ) { cityres=cities_subset.size(); break;}
  462.                         }
  463.  
  464.                         PrintWriter outp = new PrintWriter(outputfile);
  465.                         outp.println(cityres);
  466.                         for(Catapult cat : cats) {
  467.                                 if( sol.containsKey(cat) ) {
  468.                                         Tuple<Point,City> t = sol.get(cat);
  469.                                         outp.println(String.format("%d %d %d", t.first.x, t.first.y, t.second.n));
  470.                                 }else{
  471.                                         outp.println(String.format("%d %d %d", cat.x, cat.y, 0));
  472.                                 }
  473.                         }
  474.                         outp.close();
  475.  
  476.  
  477.  
  478.                 }catch(FileNotFoundException e) {
  479.                         ;
  480.                 }
  481.  
  482.         }
  483.  
  484.         public static void main(String[] args) {
  485.                 Task t = new Task();
  486.                 t.task("input.txt","output.txt");
  487.  
  488.                 long start = System.currentTimeMillis();
  489.  
  490. /*                for(int i=2;i<=48;i++)
  491.                 {
  492.                         long s = System.currentTimeMillis();
  493.                         t.task(String.format("tests/%d.in", i), String.format("tests/%d.res.txt", i));
  494.                         s = System.currentTimeMillis() - s;
  495.  
  496.                         System.out.println(String.format("test: %d , time: %d ms", i,s));
  497.                 }
  498.                 System.out.println(String.format("Total time: %d ms", System.currentTimeMillis() - start));*/
  499.  
  500.         }
  501. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!