제출 #80397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
80397		Plurm	게임판 (CEOI13_board)	C++11	40 / 100	1088 ms	1608 KiB

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);
    }

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10