fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.*;
  4.  
  5. //3/25/12 12:46 PM
  6. //by Abrackadabra
  7.  
  8. public class B {
  9.     long X;
  10.     class Segment implements Comparable<Segment> {
  11.         @Override
  12.         public int compareTo(Segment o) {
  13.             if (hash < o.hash) return -1;
  14.             if (hash > o.hash) return 1;
  15.             if (first < o.first) return -1;
  16.             if (first > o.first) return 1;
  17.             return 0;
  18.         }
  19.  
  20.         int n;
  21.         long first;
  22.  
  23.         Segment(int n, long first) {
  24.             this.n = n;
  25.             this.first = first;
  26.             hash = first ^ X;
  27.         }
  28.  
  29.         long hash;
  30.     }
  31.     public static void main(String[] args) throws IOException {
  32.         if (args.length > 0 && args[0].equals("Abra")) debugMode = true;
  33.         new B().run();
  34.     }
  35.  
  36.     int IOMode = 0; //0 - consoleIO, 1 - <taskName>.in/out, 2 - input.txt/output.txt, 3 - test case generator
  37.     String taskName = "";
  38.     ArrayList<Segment> list =new ArrayList<Segment>();
  39.     void getSegments(long L, long R, int lev){
  40.         if(R<L)
  41.             return;
  42.         if(L % 2 == 1){
  43.             list.add(new Segment(lev, L << lev));
  44.             getSegments(L+1, R,lev);
  45.             return;
  46.         }
  47.         if(R % 2 == 0){
  48.             list.add(new Segment(lev, R << lev));
  49.             getSegments(L, R - 1,lev);
  50.             return;
  51.         }
  52.         getSegments(L>>1,R>>1, lev + 1);
  53.  
  54.     }
  55.     void solve() throws IOException {
  56.         long L=nextLong();
  57.         long R=nextLong();
  58.         X=nextLong();
  59.         long K=nextLong();
  60.  
  61.         getSegments(L, R, 0);
  62.         Collections.sort(list);
  63.  
  64.         for(Segment seg : list){
  65.             if((1L << seg.n) < K){
  66.                 K-=(1L<<seg.n);
  67.                 continue;
  68.             }
  69.             out.print((((1L<<seg.n)-1 & X)^(K-1)) + seg.first);
  70.             return;
  71.         }
  72.     }
  73.  
  74.     long startTime = System.nanoTime(), tempTime = startTime, finishTime = startTime;
  75.     long startMem = Runtime.getRuntime().totalMemory(), finishMem = startMem;
  76.  
  77.     void run() throws IOException {
  78.         init();
  79.         if (debugMode) {
  80.             con.println("Start");
  81.             con.println("Console:");
  82.         }
  83.         solve();
  84.         finishTime = System.nanoTime();
  85.         finishMem = Runtime.getRuntime().totalMemory();
  86.         out.flush();
  87.         if (debugMode) {
  88.             int maxSymbols = 1000;
  89.             BufferedReader tbr = new BufferedReader(new FileReader("input.txt"));
  90.             char[] a = new char[maxSymbols];
  91.             tbr.read(a);
  92.             if (a[0] != 0) {
  93.                 con.println("File input");
  94.                 con.println(a);
  95.                 if (a[maxSymbols - 1] != 0) con.println("...");
  96.             }
  97.             tbr = new BufferedReader(new FileReader("output.txt"));
  98.             a = new char[maxSymbols];
  99.             tbr.read(a);
  100.             if (a[0] != 0) {
  101.                 con.println("File output");
  102.                 con.println(a);
  103.                 if (a[maxSymbols - 1] != 0) con.println("...");
  104.             }
  105.             con.println("Execution time: " + (finishTime - startTime) / 1000000000.0 + " sec");
  106.             con.println("Used memory:    " + (finishMem - startMem) + " bytes");
  107.             con.println("Total memory:   " + Runtime.getRuntime().totalMemory() + " bytes");
  108.         }
  109.     }
  110.  
  111.     boolean tick(double x) {
  112.         if (System.nanoTime() - tempTime > x * 1e9) {
  113.             tempTime = System.nanoTime();
  114.             con.println("Tick at " + (tempTime - startTime) / 1000000000 + " sec");
  115.             con.print("   ");
  116.             return true;
  117.         }
  118.         return false;
  119.     }
  120.  
  121.     static boolean debugMode = false;
  122.     PrintStream con = System.out;
  123.  
  124.     void init() throws IOException {
  125.         if (debugMode && IOMode != 3) {
  126.             br = new BufferedReader(new FileReader("input.txt"));
  127.             out = new PrintWriter(new FileWriter("output.txt"));
  128.         } else
  129.             switch (IOMode) {
  130.                 case 0:
  131.                     br = new BufferedReader(new InputStreamReader(System.in));
  132.                     out = new PrintWriter(System.out);
  133.                     break;
  134.                 case 1:
  135.                     br = new BufferedReader(new FileReader(taskName + ".in"));
  136.                     out = new PrintWriter(new FileWriter(taskName + ".out"));
  137.                     break;
  138.                 case 2:
  139.                     br = new BufferedReader(new FileReader("input.txt"));
  140.                     out = new PrintWriter(new FileWriter("output.txt"));
  141.                     break;
  142.                 case 3:
  143.                     out = new PrintWriter(new FileWriter("input.txt"));
  144.                     break;
  145.             }
  146.     }
  147.  
  148.     BufferedReader br;
  149.     PrintWriter out;
  150.     StringTokenizer in;
  151.  
  152.     boolean hasMoreTokens() throws IOException {
  153.         while (in == null || !in.hasMoreTokens()) {
  154.             String line = br.readLine();
  155.             if (line == null) return false;
  156.             in = new StringTokenizer(line);
  157.         }
  158.         return true;
  159.     }
  160.  
  161.     String nextString() throws IOException {
  162.         return hasMoreTokens() ? in.nextToken() : null;
  163.     }
  164.  
  165.     int nextInt() throws IOException {
  166.         return Integer.parseInt(nextString());
  167.     }
  168.  
  169.     long nextLong() throws IOException {
  170.         return Long.parseLong(nextString());
  171.     }
  172.  
  173.     double nextDouble() throws IOException {
  174.         return Double.parseDouble(nextString());
  175.     }
  176. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:8: class B is public, should be declared in a file named B.java
public class B {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/Q0qKa
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
public

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!