Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 8th, 2012  |  syntax: None  |  size: 5.15 KB  |  hits: 27  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class MainClass {
  5.     FastScanner in;
  6.     PrintWriter out;
  7.    
  8.     Set<Integer> I = new LinkedHashSet<Integer>();
  9.     Set<Integer> J = new LinkedHashSet<Integer>();
  10.     Set<Integer> swap = new LinkedHashSet<Integer>();
  11.    
  12.     ArrayList<Long> answA;
  13.     ArrayList<Long> answB;
  14.     ArrayList<Long> swAnsw;
  15.    
  16.     long [] a;
  17.     long [] b;
  18.     long [] sw;
  19.     boolean ch = false;
  20.    
  21.     int n, ridx;
  22.     long ar;
  23.     long maxEl = 0;
  24.     long currTime, maxTime;
  25.    
  26.     public void IJ() {
  27.         for (int i = 0; i < n; i++) {
  28.                 if (a[i] <= b[i]) {
  29.                         I.add(i);
  30.                         maxEl = Math.max(maxEl, a[i]);
  31.                 } else {
  32.                         J.add(i);
  33.                         maxEl = Math.max(maxEl, b[i]);
  34.                 }
  35.         }
  36.     }
  37.    
  38.     public void findMax() {
  39.         for (int i = 0; i < n; i++) {
  40.                 if (I.contains(i) && maxEl == a[i]) {
  41.                         ridx = i;
  42.                         case1();
  43.                         return;
  44.                 }
  45.         }
  46.         for (int i = 0; i < n; i++) {
  47.                 if (J.contains(i) && maxEl == b[i]) {
  48.                         ridx = i;
  49.                         case2();
  50.                         return;
  51.                 }
  52.         }
  53.     }
  54.    
  55.     public void case1() {
  56.         I.remove(ridx);
  57.         Iterator<Integer> II = I.iterator();
  58.         Iterator<Integer> JI = J.iterator();
  59.         while (II.hasNext()) {
  60.                 int i = II.next();
  61.                 answA.set(i, currTime);
  62.                 currTime += a[i];
  63.         }
  64.                 if (!JI.hasNext()) {
  65.                         if (currTime >= b[ridx]) {
  66.                         answA.set(ridx, currTime);
  67.                         } else {
  68.                                 answA.set(ridx, b[ridx]);
  69.                         }
  70.                 }
  71.         while(JI.hasNext()) {
  72.                 int i = JI.next();
  73.                 answA.set(i, currTime);
  74.                 currTime += a[i];
  75.                 if (!JI.hasNext()) {
  76.                         if (currTime >= b[ridx]) {
  77.                         answA.set(ridx, currTime);
  78.                         } else {
  79.                                 answA.set(ridx, b[ridx]);
  80.                         }
  81.                 }
  82.         }
  83.         maxTime = currTime;
  84.         currTime = 0;
  85.         answB.set(ridx, currTime);
  86.         currTime += b[ridx];
  87.         II = I.iterator();
  88.         JI = J.iterator();
  89.         while (II.hasNext()) {
  90.                 int i = II.next();
  91.                 answB.set(i, currTime);
  92.                 currTime += b[i];
  93.         }
  94.         while(JI.hasNext()) {
  95.                 int i = JI.next();
  96.                 answB.set(i, currTime);
  97.                 currTime += b[i];
  98.         }
  99.         maxTime = Math.max(maxTime, currTime);
  100.     }
  101.    
  102.     public void case2() {
  103.         J.remove(ridx);
  104.         Iterator<Integer> II = I.iterator();
  105.         Iterator<Integer> JI = J.iterator();
  106.         answA.set(ridx, currTime);
  107.         currTime += a[ridx];
  108.         while (JI.hasNext()) {
  109.                 int i = JI.next();
  110.                 answA.set(i, currTime);
  111.                 currTime += a[i];
  112.         }
  113.         while(II.hasNext()) {
  114.                 int i = II.next();
  115.                 answA.set(i, currTime);
  116.                 currTime += a[i];
  117.         }
  118.         maxTime = currTime;
  119.         currTime = 0;
  120.         II = I.iterator();
  121.         JI = J.iterator();
  122.         while (JI.hasNext()) {
  123.                 int i = JI.next();
  124.                 answB.set(i, currTime);
  125.                 currTime += b[i];
  126.         }
  127.                 if (!II.hasNext()) {
  128.                         if (currTime >= a[ridx]) {
  129.                         answB.set(ridx, currTime);
  130.                         } else {
  131.                                 answB.set(ridx, a[ridx]);
  132.                         }
  133.                 }
  134.         while(II.hasNext()) {
  135.                 int i = II.next();
  136.                 answB.set(i, currTime);
  137.                 currTime += b[i];
  138.                 if (!II.hasNext()) {
  139.                         if (currTime >= a[ridx]) {
  140.                         answB.set(ridx, currTime);
  141.                         } else {
  142.                                 answA.set(ridx, a[ridx]);
  143.                         }
  144.                 }
  145.         }
  146.         maxTime = Math.max(maxTime, currTime);
  147.     }
  148.    
  149.     void answer() {
  150.         out.write(maxTime + "\r\n");
  151.         for (int i = 0; i < n; i++) {
  152.                 out.write(answA.get(i) + " ");
  153.         }
  154.         out.write("\r\n");
  155.         for (int i = 0; i < n; i++) {
  156.                 out.write(answB.get(i) + " ");
  157.         }
  158.     }
  159.    
  160.     public void solve() throws IOException {
  161.         n = in.nextInt();
  162.         a = new long [n];
  163.         b = new long [n];
  164.         answA = new ArrayList<Long>();
  165.         answB = new ArrayList<Long>();
  166.         for (int i = 0; i < n; i++) {
  167.                 a[i] = in.nextInt();
  168.                 answA.add(0L);
  169.                 answB.add(0L);
  170.         }
  171.         for (int i = 0; i < n; i++) {
  172.                 b[i] = in.nextInt();
  173.         }
  174.         IJ();
  175.         findMax();
  176.         answer();
  177.     }
  178.  
  179.     public void run() {
  180.         try {
  181.             in = new FastScanner(new File("o2cmax.in"));
  182.             out = new PrintWriter(new File("o2cmax.out"));
  183.  
  184.             solve();
  185.  
  186.             out.close();
  187.         } catch (IOException e) {
  188.             e.printStackTrace();
  189.         }
  190.     }
  191.  
  192.     class FastScanner {
  193.         BufferedReader br;
  194.         StringTokenizer st;
  195.  
  196.         FastScanner(File f) {
  197.             try {
  198.                 br = new BufferedReader(new FileReader(f));
  199.             } catch (FileNotFoundException e) {
  200.                 e.printStackTrace();
  201.             }
  202.         }
  203.  
  204.         String next() {
  205.             while (st == null || !st.hasMoreTokens()) {
  206.                 try {
  207.                     st = new StringTokenizer(br.readLine());
  208.                 } catch (IOException e) {
  209.                     e.printStackTrace();
  210.                 }
  211.             }
  212.             return st.nextToken();
  213.         }
  214.  
  215.         int nextInt() {
  216.             return Integer.parseInt(next());
  217.         }
  218.     }
  219.  
  220.     public static void main(String[] arg) {
  221.         new MainClass().run();
  222.     }
  223. }
create a new version of this paste RAW Paste Data