제출 #1179909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179909		ace5	Ancient Machine (JOI21_ancient_machine)	C++20	5 / 100	34 ms	6344 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>

using namespace std;

namespace{
const int maxn = 100000;
const int T = 100;
}
void Anna(int N, vector<char> S)
{
    vector<__int128> fib(105);
    fib[0] = 0;
    fib[1] = 1;
    for(int j = 2;j < 105;++j)
    {
        fib[j] = fib[j-1] + fib[j-2];
    }
	vector<bool> str(maxn,false);
	bool fl = 0;
	for(int i =0;i < N;++i)
	{
		if(S[i] == 'X' && !fl)
		{
            fl = 1;
            str[i] = 1;
            i++;
		}
        else if(fl && S[i] == 'Z' && (i == N-1 || S[i+1] != 'Z'))
        {
            str[i] = 1;
            i++;
        }
	}
    for(int j = 0;j < maxn;j += T)
    {
        __int128 ans = 0;
        for(int u = j;u < j+T;++u)
        {
            ans += str[u] * fib[u-j+2];
        }
        for(int u = 0;u < 70;++u)
        {
            Send(ans%2);
            ans/=2;
        }
    }
//    cout << "!" << endl;
    return ;
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>

using namespace std;

namespace{
const int maxn = 100000;
const int T = 100;
}
void Bruno(int N, int L, vector<int> A) 
{
    vector<__int128> fib(105);
    fib[0] = 0;
    fib[1] = 1;
    for(int j = 2;j < 105;++j)
    {
        fib[j] = fib[j-1] + fib[j-2];
    }
    //cout << A.size() << endl;
    vector<bool> str(maxn);
    for(int j = 0;j < maxn/T;++j)
    {
        //cout << j << endl;
        __int128 ans = 0;
        for(int u = j*70+69;u >= j*70;--u)
        {
            ans *= 2;
            ans += A[u];
        }
        for(int u = j*T+99;u >= j*T;--u)
        {
            if(ans >= fib[u-j*T+2])
            {
                ans -= fib[u-j*T+2];
                str[u] = 1;
            }
        }
        assert(!ans);
    }
    //cout << "!" << endl;
    int start = 0;
    for(int i = 0;i < N;++i)
    {
        if(str[i])
        {
            start = i;
            break;
        }
    }
    vector<bool> rem(N,false);
    vector<int> tr;
    for(int i = start+1;i < N;++i)
    {
        if(str[i])
        {
            for(int j = int(tr.size()-1);j >= 0;--j)
            {
                rem[tr[j]] = 1;
                Remove(tr[j]);
            }
            tr.clear();
            rem[i] = 1;
            Remove(i);
        }
        else
            tr.push_back(i);
    }
    for(int i = 0;i < N;++i)
    {
        if(!rem[i])
        {
            Remove(i);
        }
    }
    //cout << "!" << endl;
    return ;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 95