답안 #80397 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
80397	2018-10-20T13:44:38 Z	Plurm	게임판 (CEOI13_board)	C++11	40 / 100	200 ms	1608 KB

board

    #include <bits/stdc++.h>
    using namespace std;
    char a[100005];
    char b[100005];
    class holder : public vector<bool> {
      public:
      vector<int> hsh;
      inline int ghash(){
        return size() <= 20 ? -1 : hsh[size()-21];
      }
      inline int to_int(){
        int v = 1;
        for(int i = max((int)size()-20,0); i < size(); i++){
          v *= 2;
          if(at(i)) v++;
        }
        return v;
      }
      void push_back(bool b){
        vector<bool>::push_back(b);
        if(hsh.empty()) hsh.push_back(b ? 1 : 0);
        else hsh.push_back((53*hsh.back() + (b ? 1 : 0)) % 1000003);
      }
      void pop_back(){
        vector<bool>::pop_back();
        hsh.pop_back();
      }
    };
    inline void mmove(holder& x,char y){
      int i;
      switch(y){
        case '1':
          x.push_back(false);
          break;
     
        case '2':
          x.push_back(true);
          break;
     
        case 'U':
          x.pop_back();
          break;
     
        case 'L':
          for(i = x.size()-1; i >= 0; i--){
            if(x[i]){
              x[i] = false;
              break;
            }else{
              x[i] = true;
            }
          }
          for(; i < x.size(); i++){
            if(i == 0) x.hsh[i] = x[i] ? 1 : 0;
            else x.hsh[i] = (x.hsh[i-1]*53 + (x[i] ? 1 : 0)) % 1000003;
          }
          break;
     
        case 'R':
          for(i = x.size()-1; i >= 0; i--){
            if(x[i]){
              x[i] = false;
            }else{
              x[i] = true;
              break;
            }
          }
          for(; i < x.size(); i++){
            if(i == 0) x.hsh[i] = x[i] ? 1 : 0;
            else x.hsh[i] = (x.hsh[i-1]*53 + (x[i] ? 1 : 0)) % 1000003;
          }
          break;
      }
    }
    inline int glv(int x){
      int l = 0;
      while(x > 1){
        x /= 2;
        l++;
      }
      return l;
    }
    pair<int,int> mem[100005];
    int main(){
      gets(a);
      gets(b);
      holder ma;
      holder mb;
      for(int i = 0; a[i]; i++){
        mmove(ma,a[i]);
      }
      for(int i = 0; b[i]; i++){
        mmove(mb,b[i]);
      }
      if(ma.size() < mb.size()){
        for(int i = 0; i < 100005; i++){
          swap(a[i],b[i]);
        }
        swap(ma,mb);
      }
      int lla = ma.size();
      while(!ma.empty()){
        mem[ma.size()] = make_pair(ma.ghash(),ma.to_int());
        ma.pop_back();
      }
      int llb = mb.size();
      int d = lla + llb;
      while(!mb.empty()){
        if(mb.ghash() == mem[mb.size()].first){
          d = min(d,(int)(lla - mb.size() + llb - mb.size() + abs(mb.to_int() - mem[mb.size()].second)));
        }
        mb.pop_back();
      }
      printf("%d\n",d);
    }

Compilation message

board.cpp: In member function 'int holder::to_int()':
board.cpp:13:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = max((int)size()-20,0); i < size(); i++){
                                            ~~^~~~~~~~
board.cpp: In function 'void mmove(holder&, char)':
board.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(; i < x.size(); i++){
                 ~~^~~~~~~~~~
board.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(; i < x.size(); i++){
                 ~~^~~~~~~~~~
board.cpp: In function 'int main()':
board.cpp:85:13: warning: 'char* gets(char*)' is deprecated [-Wdeprecated-declarations]
       gets(a);
             ^
In file included from /usr/include/c++/7/cstdio:42:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:46,
                 from board.cpp:1:
/usr/include/stdio.h:638:14: note: declared here
 extern char *gets (char *__s) __wur __attribute_deprecated__;
              ^~~~
board.cpp:86:13: warning: 'char* gets(char*)' is deprecated [-Wdeprecated-declarations]
       gets(b);
             ^
In file included from /usr/include/c++/7/cstdio:42:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:46,
                 from board.cpp:1:
/usr/include/stdio.h:638:14: note: declared here
 extern char *gets (char *__s) __wur __attribute_deprecated__;
              ^~~~
board.cpp:85:11: warning: ignoring return value of 'char* gets(char*)', declared with attribute warn_unused_result [-Wunused-result]
       gets(a);
       ~~~~^~~
board.cpp:86:11: warning: ignoring return value of 'char* gets(char*)', declared with attribute warn_unused_result [-Wunused-result]
       gets(b);
       ~~~~^~~
/tmp/ccuAvdqd.o: In function `main':
board.cpp:(.text.startup+0x2a): warning: the `gets' function is dangerous and should not be used.

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	708 KB	Output is correct
2	Correct	3 ms	708 KB	Output is correct
3	Correct	6 ms	968 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	968 KB	Output is correct
2	Correct	2 ms	1040 KB	Output is correct
3	Correct	2 ms	1168 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1168 KB	Output is correct
2	Correct	9 ms	1220 KB	Output is correct
3	Correct	4 ms	1220 KB	Output is correct
4	Correct	2 ms	1220 KB	Output is correct
5	Correct	2 ms	1220 KB	Output is correct

Subtask #5
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1220 KB	Output is correct
2	Correct	2 ms	1220 KB	Output is correct
3	Incorrect	2 ms	1220 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1220 KB	Output is correct
2	Correct	4 ms	1220 KB	Output is correct
3	Incorrect	3 ms	1220 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1220 KB	Output is correct
2	Correct	6 ms	1220 KB	Output is correct
3	Correct	4 ms	1220 KB	Output is correct
4	Incorrect	2 ms	1220 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1062 ms	1568 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1077 ms	1568 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1088 ms	1608 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-