fork download
copy 
  1. #include <stdio.h>
  2. #include <deque>
  3. #include <set>
  4. #include <map>
  5. #include <vector>
  6. #include <utility>
  7. #include <stdexcept>
  8. #include <bitset>
  9.  
  10. //http://w...content-available-to-author-only...f.com/NOV12/problems/JABO
  11. typedef unsigned offset_type;
  12. typedef unsigned voltage_type;
  13. typedef std::pair<offset_type, unsigned> cell_type;
  14. struct group {
  15.     offset_type offset;
  16.     voltage_type voltage;
  17.     inline explicit group(offset_type o=0):offset(o),voltage(0){}
  18. };
  19. struct jam {
  20.     std::vector<group> connections;
  21.  
  22.     inline jam(offset_type size) :connections(size)
  23.     { for(offset_type i=0; i<connections.size(); ++i)connections[i] = group(i); }
  24.     inline group& get_top(offset_type a) {
  25.         const unsigned max_depth=20;
  26.         while(connections.at(a).offset!=a) {
  27.             offset_type orig = a;
  28.             for(unsigned td=0; connections.at(a).offset!=a && td<max_depth; ++td)
  29.                 a = connections[a].offset; 
  30.             connections[orig].offset = a;
  31.         }
  32.         return connections[a];
  33.     }
  34.     inline void add_wire(offset_type one, offset_type two) {
  35.         group& topone = get_top(one);
  36.         group& toptwo = get_top(two);
  37.         if (&topone != &toptwo) {
  38.             toptwo.offset = topone.offset; 
  39.             topone.voltage += toptwo.voltage;
  40.         }
  41.     }
  42.     inline void add_voltage(cell_type one) { 
  43.         group& v = get_top(one.first);
  44.         if ((++v.voltage) == 0) throw std::logic_error("too many voltages");
  45.     }
  46.     inline void remove_voltage(cell_type one) { 
  47.         group& v = get_top(one.first);
  48.         if ((v.voltage--) == 0)throw std::logic_error("too few voltages");
  49.     }
  50.     inline void try_LED(offset_type one, offset_type two) {
  51.         bool ov = get_top(one).voltage>0;
  52.         bool tv = get_top(two).voltage>0;
  53.         if (ov != tv) printf("ON\n");
  54.         else printf("OFF\n");
  55.     }
  56.     inline void print(unsigned columns) {
  57. #ifdef _DEBUG
  58.         printf("\n");
  59.         for(unsigned r=0;r<connections.size()/columns; ++r) {
  60.             for(unsigned c=0;c<columns;++c) {
  61.                 offset_type o=r*columns+c;
  62.                 printf("%d%c", connections[o].offset, (connections[o].voltage ? '*' : ' '));
  63.             }
  64.             printf("\n");
  65.         }
  66. #endif
  67.     }
  68. };
  69. inline unsigned base52(char i) {
  70.     if (i>='A' && i<='Z')
  71.         return i-'A';
  72.     else if (i>='a' && i<='z')
  73.         return i-'a'+26;
  74.     throw std::logic_error("b52");
  75. }
  76. inline unsigned read_digit() {
  77.     char a=0,b=0;
  78.     if(scanf("%c%c",&a,&b)!=2) throw std::logic_error("ab");
  79.     return base52(a)*52+base52(b);
  80. }
  81. inline cell_type read_coord(int columns) {
  82.     unsigned x = read_digit()-1;
  83.     unsigned y = read_digit()-1;
  84. #ifdef _DEBUG
  85.     printf("%d ", x+y/5*columns);
  86. #endif
  87.     return cell_type(x+y/5*columns, y%5);
  88. }
  89. int go() {
  90.     unsigned l=0,c=0,r=0;
  91.     //why is this input r/c instead of the other way around?
  92.     if(scanf("%u %u %u",&l,&r,&c)!=3) throw std::logic_error("lrc"); 
  93.     if (c>2500) throw std::logic_error("l");//2500c, 500r max
  94.     if (r>500) throw std::logic_error("r");
  95.     jam j(r*c); 
  96.     for(unsigned i=0; i<l; ++i) {
  97.         char t=0;
  98.         if(scanf(" %c",&t)!=1) throw std::logic_error("t");
  99.         switch(t) {
  100.         case 'W': j.add_wire(read_coord(c).first, read_coord(c).first); break;
  101.         case 'V': j.add_voltage(read_coord(c)); break;
  102.         case 'R': j.remove_voltage(read_coord(c)); break;
  103.         case 'L': j.try_LED(read_coord(c).first, read_coord(c).first); break;
  104.         default: throw std::logic_error("t"); break;
  105.         }
  106.         j.print(c);
  107.     }
  108.     return 0;
  109. }
  110.  
  111. //#include <ctime>
  112. int main() {
  113.     int r = 0;
  114.     //clock_t start = clock();
  115.     //for(int i=0; i<1000;++i)
  116.         r = go();
  117.     //double dur = double(clock()-start)/CLOCKS_PER_SEC;
  118.     //printf("1000 ticks over %fs at %fs each.", dur, dur/1000.0);
  119.     return r;
  120. }
  121.  
  122. /*
  123. Input:
  124. 9 2 10
  125. WADAEAFAG
  126. VAGAD
  127. LAFAHAGAE
  128. VAKAK
  129. LAJAKAKAJ
  130. LAKAIAGAB
  131. LABABACAB
  132. RAKAK
  133. LAJAKAKAJ
  134.  
  135. Output:
  136. ON
  137. ON
  138. OFF
  139. OFF
  140. OFF
  141. */
  142.  
Runtime error #stdin #stdout 0s 3072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hnL7mC
language:
C++14 (gcc 8.3)
created:
11 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!