#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
namespace {
const int maxn = 1e5+5;
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
int variable_example = 0;
const int maxbit = 7e4;
const int len = maxbit / 60;
const ll cap = (1ull<<60)-1;
struct bint{
ll * a;
bint(){
a = new ll[len];
memset(a, 0, len * sizeof (ll)) ;
}
bint(ll x) {
a = new ll[len];
memset(a, 0, len * sizeof (ll));
a[0] = x;
}
bint(bint &b) {
a = new ll[len];
REP(i,len) a[i] = b.a[i];
}
void add(bint &b) {
for (int i = 0; i<len-1; ++i) {
a[i] += b.a[i];
a[i+1] += a[i] >> 60;
a[i] &= cap;
}
}
void sub(bint b) { // if b > this, terrible things will happen!!!
for (int i = 0; i<len-1; ++i) {
a[i] -= b.a[i];
if (a[i] < 0) {
a[i] += (1ll<<60);
a[i+1] --;
}
}
}
vector<int> spit(){
vector<int> ret;
for (int i = 0; i<len-1; ++i) {
REP(j,60) {
ret.pb((a[i]>>j)&1);
}
}
while (!ret.empty() && ret.back() == 0) ret.pop_back();
return ret;
}
void eat(vector<int> v) {
REP(i, SZ(v)) {
if (v[i])
a[i/60] |= (1ll << (i%60));
}
}
bool geq(bint b) {
RREP(i,len) {
if (a[i] > b.a[i]) return 1;
if (a[i] < b.a[i]) return 0;
}
return 1;
}
};
}
//#ifdef BALBIT
//void Send(int x) {
// bug("Sent: ", x);
//}
//#endif // BALBIT
void Anna(int n, std::vector<char> S) {
vector<int> ret(n);
bool zed = 0;
int wherezed = n;
for (int i = n-1; i>=0; --i) {
if (S[i] == 'Z' && !zed) {
zed = 1;
wherezed = i;
}
else if (S[i] == 'X' && zed && (i==0 || S[i-1] != 'X')) {
ret[i] = 1;
}
}
// Send wherezed
REP(i, 17) {
Send((wherezed>>i)&1);
}
bint f0 (0);
bint f1 (1);
bint sum (0);
REP(i, n) {
// position 0: 1, position 1: 2, position 2: 3, position 3: 5, etc
// bug(i, f0.a[0], f1.a[0]);
if (ret[i] == 0 && (i==0 || ret[i-1] != 0)) {
// fib.pb(1);
bug(1);
}else if (ret[i] == 1){
// fib.pb(2);
bug(2);
sum.add(f1);
// ++i;
}
bint tmp = bint(f1);
tmp.add(f0);
f0 = f1;
f1=tmp;
}
bug(sum.a[0]);
vector<int> tosend = sum.spit();
// for (int x : fib) cout<<x<<' ';
// cout<<endl;
REP(i,SZ(tosend)) {
bug( i);
Send(tosend[i]);
}
}
//int main(){
// Anna(6, {'Z','X','Y','X','Z','Z'});
//}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
namespace {
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
const int maxn = 1e5+5;
int variable_example = 0;
int FunctionExample(int P) { return 1 - P; }
const int maxbit = 7e4;
const int len = maxbit / 60;
const ll cap = (1ull<<60)-1;
struct bint{
ll * a;
bint(){
a = new ll[len];
memset(a, 0, len * sizeof (ll)) ;
}
bint(ll x) {
a = new ll[len];
memset(a, 0, len * sizeof (ll));
a[0] = x;
}
bint(bint &b) {
a = new ll[len];
REP(i,len) a[i] = b.a[i];
}
void add(bint &b) {
for (int i = 0; i<len-1; ++i) {
a[i] += b.a[i];
a[i+1] += a[i] >> 60;
a[i] &= cap;
}
}
void sub(bint b) { // if b > this, terrible things will happen!!!
for (int i = 0; i<len-1; ++i) {
a[i] -= b.a[i];
if (a[i] < 0) {
a[i] += (1ll<<60);
a[i+1] --;
}
}
}
vector<int> spit(){
vector<int> ret;
for (int i = 0; i<len-1; ++i) {
REP(j,60) {
ret.pb((a[i]>>j)&1);
}
}
while (ret.back() == 0) ret.pop_back();
return ret;
}
void eat(vector<int> v) {
REP(i, SZ(v)) {
if (v[i])
a[i/60] |= (1ll << (i%60));
}
}
bool geq(bint b) {
RREP(i,len) {
if (a[i] > b.a[i]) return 1;
if (a[i] < b.a[i]) return 0;
}
return 1;
}
};
int far[maxn];
} // namespace
void Bruno(int n, int L, std::vector<int> A) {
// if (*max_element(ALL(A)) == 0) {
// }
int zpos = 0;
REP(i,17){
zpos += A[i] << i ;
}
if (zpos == n) {
REP(i,n) {
Remove(i);
}
return;
}
bug(zpos);
vector<int> rest;
for (int i = 17; i<SZ(A); ++i) {
rest.pb(A[i]);
}
bint code = bint();
code.eat(rest);
bint f0 = bint(0);
bint f1 = bint(1);
int at = 0; // considering position
while (code.geq(f1)) {
bint tmp = bint(f1);
tmp.add(f0);
f0 = f1;
f1 = tmp;
++at;
}
while (at >= 1) {
if (code.geq(f0)) {
code.sub(f0);
far[at-1] = 1;
bug("Took ", at);
}
bint tmp = bint(f1);
tmp.sub(f0);
f1 = f0;
f0 = tmp;
--at;
}
bug(code.a[0]);
vector<int> Yay;
int tit = 0;
while (SZ(Yay) < n) {
if (far[tit]) {
Yay.pb(1);
}
else Yay.pb(0);
bug(Yay.back());
++tit;
}
Yay[zpos] = 1;
bug(zpos);
for (int i = n-1; i>=0; --i) {
if (Yay[i] == 1) {
zpos = i;
break;
}else{
Remove(i);
}
}
int prv = zpos;
for (int i = zpos-1; i>=0; --i) {
if (Yay[i] == 1 || i == 0) {
// met an x
for (int j = i+1; j<prv; ++j) {
Remove(j);
}
Remove(i);
prv = i;
}
}
Remove(zpos);
}
Compilation message
Anna.cpp:42:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
42 | int variable_example = 0;
| ^~~~~~~~~~~~~~~~
Bruno.cpp:42:5: warning: 'int {anonymous}::FunctionExample(int)' defined but not used [-Wunused-function]
42 | int FunctionExample(int P) { return 1 - P; }
| ^~~~~~~~~~~~~~~
Bruno.cpp:40:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
40 | int variable_example = 0;
| ^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1784 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1904 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2160 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2156 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
2284 KB |
Wrong Answer [6] |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
300 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
