fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class TaskD {
  5.     private final InputReader reader;
  6.     private final OutputWriter writer;
  7.  
  8.     public TaskD(InputReader reader, OutputWriter writer) {
  9.         this.reader = reader;
  10.         this.writer = writer;
  11.     }
  12.  
  13.     public static void main(String[] args) {
  14.         InputReader reader = new InputReader(System.in);
  15.         OutputWriter writer = new OutputWriter(System.out);
  16.         new TaskD(reader, writer).run();
  17.         writer.writer.flush();
  18.     }
  19.  
  20.     int[] col;
  21.     List<Integer>[] E;
  22.  
  23.     int[] A, B;
  24.     int to(int e, int x) {
  25.         return A[e] ^ B[e] ^ x;
  26.     }
  27.  
  28.     int[] ept;
  29.     void DFS(int x, int f) {
  30.         while (ept[x] != E[x].size() && col[E[x].get(ept[x])] != -1)
  31.             ept[x]++;
  32.         if (ept[x] == E[x].size())
  33.             return;
  34.         int e = E[x].get(ept[x]++);
  35.         col[e] = f;
  36.         DFS(to(e, x), 1 - f);
  37.     }
  38.  
  39.     public void run() {
  40.         int n = reader.nextInt();
  41.         final int N = 200500;
  42.         E = new List[3 * N];
  43.         for (int i = 0; i < 3 * N; i++)
  44.             E[i] = new ArrayList<Integer>();
  45.         int[] X = new int[N];
  46.         int[] Y = new int[N];
  47.         A = new int[3 * N];
  48.         B = new int[3 * N];
  49.         ept = new int[3 * N];
  50.         col = new int[3 * N];
  51.         Arrays.fill(col, -1);
  52.         for (int i = 0; i < n; i++) {
  53.             X[i] = reader.nextInt() - 1;
  54.             Y[i] = reader.nextInt() - 1;
  55.             A[i] = X[i];
  56.             B[i] = Y[i] + N;
  57.             E[X[i]].add(i);
  58.             E[Y[i] + N].add(i);
  59.         }
  60.         int pt = 2 * N;
  61.         int ppt = N;
  62.         int parity = 0;
  63.  
  64.         boolean was = false;
  65.         for (int i = 0; i < 2 * N; i++)
  66.             if (E[i].size() % 2 == 1) {
  67.                 if (parity == 1 && ppt > N && A[ppt - 1] < N && i >= N && !was) {
  68.                     B[ppt - 1] = i;
  69.                     E[i].add(ppt - 1);
  70.                     parity = 0;
  71.                     was = true;
  72.                 } else {
  73.                     A[ppt] = i;
  74.                     B[ppt] = pt;
  75.                     E[A[ppt]].add(ppt);
  76.                     E[B[ppt]].add(ppt);
  77.                     ppt++;
  78.                     if (parity == 0)
  79.                         parity = 1;
  80.                     else {
  81.                         pt++;
  82.                         parity = 0;
  83.                     }
  84.                 }
  85.             }
  86.         if (parity == 1)
  87.             throw new AssertionError();
  88.         for (int i = 0; i < 2 * N; i++) {
  89.             DFS(i, 0);
  90.         }
  91.         char[] ans = new char[n];
  92.         for (int i = 0; i < n; i++) {
  93.             if (col[i] == -1)
  94.                 throw new AssertionError();
  95.             ans[i] = col[i] == 1 ? 'r' : 'b';
  96.         }
  97.         writer.printf("%s\n", String.valueOf(ans));
  98.     }
  99.  
  100.  
  101.     static class InputReader {
  102.         public BufferedReader reader;
  103.         public StringTokenizer tokenizer;
  104.  
  105.         public InputReader(InputStream stream) {
  106.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  107.             tokenizer = null;
  108.         }
  109.  
  110.         public String next() {
  111.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  112.                 try {
  113.                     tokenizer = new StringTokenizer(reader.readLine());
  114.                 } catch (IOException e) {
  115.                     throw new RuntimeException(e);
  116.                 }
  117.             }
  118.             return tokenizer.nextToken();
  119.         }
  120.  
  121.         public int nextInt() {
  122.             return Integer.parseInt(next());
  123.         }
  124.  
  125.         public double nextDouble() {
  126.             return Double.parseDouble(next());
  127.         }
  128.  
  129.         public long nextLong() {
  130.             return Long.parseLong(next());
  131.         }
  132.     }
  133.  
  134.     static class OutputWriter {
  135.         public PrintWriter writer;
  136.  
  137.         OutputWriter(OutputStream stream) {
  138.             writer = new PrintWriter(stream);
  139.         }
  140.  
  141.         public void printf(String format, Object... args) {
  142.             writer.print(String.format(Locale.ENGLISH, format, args));
  143.         }
  144.     }
  145. }
  146.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:4: error: class TaskD is public, should be declared in a file named TaskD.java
public class TaskD {
       ^
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
stdout
copy 
Standard output is empty
https://ideone.com/p5VlGg
language:
Java (12.0.1)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!