oj.uz

Submission #537869

# Submission time Handle Problem Language Result Execution time Memory
537869 2022-03-15T17:57:24 Z Jarif_Rahman Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 369 ms 8236 KB 
#include "Anna.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

namespace {
    vector<ll> fib(60, 0);

    void send_number(ll x){
        for(int i = 0; i < 35; i++){
            Send(x%2);
            x/=2;
        }
    }

    void send_encoded(vector<int> v){
        int n = v.size();
        while(n%50 != 0) n++, v.pb(0);
        for(int i = 0; i < n; i+=50){
            vector<ll> dp(50, 0);
            if(v[i] == 0 && v[i+1] == 0) dp[0] = 0, dp[1] = 0;
            else if(v[i] == 0 && v[i+1] == 1) dp[0] = 0, dp[1] = fib[3]+dp[0];
            else if(v[i] == 1 && v[i+1] == 0) dp[0] = 1, dp[1] = 1;
            for(int j = i+2; j < i+50; j++){
                if(v[j] == 0) dp[j-i] = dp[j-i-1];
                else dp[j-i] = fib[j-i+2]+dp[j-i-2];
            }
            //for(ll x: dp) cerr << x << " ";
            //cerr << " Anna dp\n";
            send_number(dp[49]);
        }
    }
}

void Anna(int n, vector<char> s){

    fib[1] = 1;
    for(int i = 2; i < 60; i++) fib[i] = fib[i-1]+fib[i-2];

    vector<int> rt(n, 0);
    int fx = -1;
    for(int i = 0; i < n; i++) if(s[i] == 'X'){
        fx = i;
        break;
    }

    if(fx == -1){
        send_encoded(rt);
        send_number(0);
        return;
    }

    //rt[fx] = 1;

    for(int i = fx+1; i < n; i++) if(s[i] == 'Z' && (i == n-1 || s[i+1] != 'Z')) rt[i] = 1;

    //for(int x: rt) cerr << x << " "; cerr << " Anna\n";

    send_encoded(rt);
    send_number(fx);
}
#include "Bruno.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

namespace {
    vector<ll> fib(60, 0);

    ll get_number(vector<int> x){
        ll rt = 0;
        for(int i = 34; i >= 0; i--){
            if(x[i] == 1) rt+=(1LL<<i);
        }
        return rt;
    }

    vector<int> decode(vector<int> v){
        vector<int> rt;
        int n = v.size();
        for(int i = 0; i < n; i+=35){
            vector<int> sth;
            for(int j = 0; j < i+35; j++) sth.pb(v[j]);
            ll c = get_number(sth);
            vector<int> cur;
            for(int j = 49; j >= 0; j--){
                if(c >= fib[j+2]){
                    cur.pb(1);
                    cur.pb(0);
                    c-=fib[j+2];
                    j--;
                }
                else{
                    cur.pb(0);
                }
            }
            if(cur.size() > 50) cur.pop_back();
            reverse(cur.begin(), cur.end());
            rt.insert(rt.end(), cur.begin(), cur.end());
        }
        return rt;
    }
}

void Bruno(int n, int m, vector<int> A){
    fib[1] = 1;
    for(int i = 2; i < 60; i++) fib[i] = fib[i-1]+fib[i-2];

    vector<int> sth;
    for(int i = 0; i < 35; i++){
        sth.pb(A.back());
        A.pop_back();
    }
    reverse(sth.begin(), sth.end());
    int fx = get_number(sth);

    A = decode(A);
    while(A.size() != n) A.pop_back();

    //for(int x: A) cerr << x << " "; cerr << " Bruno\n";

    for(int i = 0; i < fx; i++) Remove(i);

    int ls = fx+1;
    
    for(int i = fx+1; i < n; i++){
        if(A[i] != 1) continue;
        for(int j = i-1; j >= ls; j--) Remove(j);
        Remove(i);
        ls = i+1;
    }

    Remove(fx);

    for(int i = ls; i < n; i++) Remove(i);
}

Compilation message

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:61:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |     while(A.size() != n) A.pop_back();
      |           ~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 508 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 1 ms 516 KB Output is correct
5 Correct 0 ms 560 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 0 ms 508 KB Output is correct
8 Correct 0 ms 516 KB Output is correct
9 Correct 0 ms 508 KB Output is correct
10 Correct 1 ms 556 KB Output is correct
11 Correct 0 ms 516 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 369 ms 8236 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -