| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 664363 | blue | Ancient Machine (JOI21_ancient_machine) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "Anna.h"
#include <bits/stdc++.h>
namespace
{
using namespace std;
using vi = vector<int>;
const int obs = 60;
const int cbs = 40;
vi encode(vi A)
{
while(sz(A) % obs != 0)
A.push_back(0);
ll pow2[cbs];
pow2[0] = 1;
for(int i = 1; i < cbs; i++)
pow2[i] = pow2[i-1] * 2LL;
ll dp[1 + obs][2];
dp[1][0] = 1;
dp[1][1] = 1;
for(int i = 2; i <= obs; i++)
{
dp[i][0] = dp[i-1][0] + dp[i-1][1];
dp[i][1] = dp[i-1][0];
}
vi res;
for(int i = 0; i < sz(A); i += obs)
{
vi a;
ll val = 0;
for(int j = i; j < i + obs; j++)
{
a.push_back(A[j]);
}
for(int j = 0; j < obs; j++)
{
if(a[j] == 1)
{
val += dp[obs - j][0];
}
}
for(int j = 0; j < cbs; j++)
res.push_back(bool(val & pow2[j]));
}
return res;
}
}
void Anna(int N, vector<char> S)
{
// cerr << "hello\n";
int fx = 0;
int lz = N-1;
while(fx < N && S[fx] != 'X')
fx++;
while(lz >= 0 && S[lz] != 'Z')
lz--;
if(fx == N || lz == -1)
{
// cerr << "hello2\n";
return;
}
vi tosend(N+1, 0);
tosend[fx] = 1;
tosend[lz+1] = 1;
for(int i = fx+2; i <= lz-1; i++)
{
if(S[i-1] == 'Z' && S[i] == 'Y')
tosend[i] = 1;
}
// for(int i = 0; i <= N; i++)
// cerr << tosend[i];
// cerr << '\n';
tosend = encode(tosend)
for(int f : tosend)
Send(f);
}
#include "Bruno.h"
#include <bits/stdc++.h>
namespace
{
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using ll = long long;
using vll = vector<ll>;
const int obs = 60;
const int cbs = 40;
vi decode(vi A, int S) //S = size of decoded sequence
{
assert(sz(A) % cbs == 0);
vi res;
for(int i = 0; i < sz(A); i += cbs)
{
vll a;
for(int j = i; j < i+cbs; j++)
a.push_back(A[j]);
ll pow2[cbs];
pow2[0] = 1;
for(int i = 1; i < cbs; i++)
pow2[i] = pow2[i-1] * 2LL;
ll val = 0;
for(int j = 0; j < cbs; j++)
val += pow2[j] * a[j];
ll dp[1 + obs][2];
dp[1][0] = 1;
dp[1][1] = 1;
for(int i = 2; i <= obs; i++)
{
dp[i][0] = dp[i-1][0] + dp[i-1][1];
dp[i][1] = dp[i-1][0];
}
for(int j = 0; j < obs; j++)
{
if(dp[obs - j][0] >= val)
res.push_back(0);
else
{
val -= dp[obs - j][0];
res.push_back(1);
res.push_back(0);
j++;
}
}
}
while(sz(res) > S)
res.pop_back();
return res;
}
}
void Bruno(int N, int L, vi A)
{
if(A.empty())
{
for(int i = 0; i < N; i++)
Remove(i);
return;
}
A = decode(A, N+1);
int lz = N;
while(A[lz] != 1)
lz--;
lz--;
int fx = 0;
while(A[fx] != 1)
fx++;
// cerr << fx << ' ' << lz << '\n';
for(int i = 0; i < fx; i++)
Remove(i);
for(int i = lz+1; i < N; i++)
Remove(i);
vi st;
for(int i = fx+1; i <= lz; i++)
{
if(i < lz && A[i+1] == 0)
{
// cerr << "add " << i << " to stack\n";
st.push_back(i);
}
else
{
while(!st.empty())
{
Remove(st.back());
// cerr << "pop " << st.back() << '\n';
st.pop_back();
}
Remove(i);
// cerr << "remove Z : " << i << '\n';
}
}
Remove(fx);
// cerr << "final remove " << fx << '\n';
}