CodeJamTemplate/examples/2021/Round1C/C/diff_Main.cpp at master · demmerichs/CodeJamTemplate · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
diff --git a/CodeJam/Main.cpp b/examples/2021/Round1C/C/Main.cpp
index 2150379..9d50956 100644
--- a/CodeJam/Main.cpp
+++ b/examples/2021/Round1C/C/Main.cpp
@@ -1,5 +1,5 @@
-// #define DEFAULT_VAL_MODE    //remove comment on this line, to activate default value trigger
-#define DEFAULT_VAL_TRIGGER result.sz == 0
+#define DEFAULT_VAL_MODE    //remove comment on this line, to activate default value trigger
+#define DEFAULT_VAL_TRIGGER result == -1
 #define DEFAULT_VAL "IMPOSSIBLE"
 // #define IA_MODE        //remove comment on this line, to activate interactive problem mode
 #define IA_ERROR_CODE -1
@@ -1570,11 +1570,111 @@ void init(){
     cin >> T;
 }

+str S, E;
+
 void readInput(){
+    cin >> S >> E;
 }

 // write to COMM_TYPE result
 void calcFunction() {
+    result = 0;
+    if(S==E){
+        return;
+    }
+    if(S=="0"){
+        result = 1;
+        S = "1";
+    }
+
+    dq(ll) s, e;
+    lg(S);
+    lg(E);
+    forn(i, S.sz){
+        if(S[i]-'0' == s.sz%2){
+            s.bk++;
+        } else {
+            s.pb(1);
+        }
+    }
+    if(E!="0"){
+        forn(i, E.sz){
+            if(E[i]-'0' == e.sz%2){
+                e.bk++;
+            } else {
+                e.pb(1);
+            }
+        }
+    }
+    lg(s);
+    lg(e);
+    if(E=="0"){
+        result += s.sz;
+        return;
+    }
+
+    if(s.sz + (s.sz%2) < e.sz){
+        result = -1;
+        return;
+    }
+
+    while(s.sz > (e.sz+1)/2*2){
+        s.popf;
+        result++;
+    }
+    while(s!=e){
+        ll pivot = max<ll>(s.sz-e.sz, 0LL);
+        while(true){
+            if(pivot == s.sz) break;
+            bool pivot_works = true;
+            fornn(i, pivot, s.sz-1){
+                if(s[i]!=e[i-pivot]){
+                    pivot_works=false;
+                    break;
+                }
+            }
+            if(s.bk > e[s.sz-pivot-1]) pivot_works=false;
+            if(s.sz%2==1){
+                if(s.bk < e[s.sz-pivot-1]) pivot_works=false;
+            }
+            if(pivot_works){
+                break;
+            } else {
+                pivot++;
+            }
+        }
+        lg(s);
+        lg(e);
+        lg(pivot);
+        if(pivot == s.sz){
+            if(s.sz % 2 == 0){
+                s.popf;
+                result++;
+                pivot--;
+                continue;
+            } else {
+                s.pb(1);
+                result++;
+                continue;
+            }
+        }
+        if(s.sz%2==0){
+            if(s.bk < e[s.sz-pivot-1]){
+                s.bk++;
+                result++;
+                continue;
+            }
+            if(s.bk == e[s.sz - pivot-1]){
+                s.popf;
+                pivot--;
+                result++;
+                continue;
+            }
+        } else {
+            s.pb(1);
+            result++;
+        }
+    }
 }

 } // namespace task