Submission #1064220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064220		8e7	Tricolor Lights (JOI24_tricolor)	C++17	40 / 100	118 ms	8344 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);




int to_int(char c) {
    if (c == 'R') return 0;
    else if (c == 'G') return 1;
    else return 2;
}

char to_char(int i) {
    const string S = "RGB";
    return S[i];
}

int base_one(int prv, int res) {
    if ((prv+1)%3 != res) return (prv+1)%3;
    else return (prv+2)%3;
}

int diff(int a, int b) {
    //returns a number from 0~2 different from both a and b
    if ((a+1)%3 == b) return (a+2)%3;
    else return (a+1)%3;
}

int fib[30];
const int maxfib = 28;
}
void add_bit(std::vector<int> &ret, std::vector<int> &v, int bit) {
    //add semantic bit, could be 0/1/2
    int ind = ret.size();
    if (ind >= v.size()) return;
    for (int i = 0;i < bit*2;i++) {
        ret.push_back(base_one(ret.back(), v[ind])); 
        ind++;
        if (ind >= v.size()) return;
    }
    if (ret.back() != v[ind]) {
        ret.push_back(ret.back()); //base 0
        ind++;
    } else {
        if (ind+1 >= v.size()) {
            ret.push_back(base_one(ret.back(), v[ind]));
            return;
        }
        ret.push_back(base_one(ret.back(), v[ind+1])); 
        ret.push_back(ret.back());
        ind+=2; 
    }
}

pair<string, int> anna(int N, string S) {
    fib[0] = fib[1] = 1;
    for (int i = 2;i < 29;i++) fib[i] = fib[i-1] + fib[i-2]; 
    

    vector<int> v(N, 0), ret;
    for (int i = 0;i < N;i++) v[i] = to_int(S[i]);
    ret.push_back((v[0]+1)%3);
    int maxlen = 0;
    vector<int> bigarr;
    while (ret.size() < N) {
        int pos = ret.size();
        //try to encode pos
        vector<int> bi;
        int dis = maxfib;
        while (dis > 0) {
            if (pos >= fib[dis-1]) {
                bi.push_back(1);
                pos -= fib[dis-1];
                dis -= 2;
            } else {
                dis--;
                bi.push_back(0);
            }
        }
        int len = 0;
        for (int b:bi) {
            len += (b+1)*2;
            add_bit(ret, v, b);
        } 
        if (len > maxlen) {
            bigarr = bi;
        }
        maxlen = max(maxlen, len); 
        add_bit(ret, v, 2); //add separator
    }
    pary(bigarr.begin(), bigarr.end());
    int L = min(N, maxlen*2+6);
    string ans;
    for (int i = 0;i < N;i++) {
        ans.push_back(to_char(ret[i]));
    }
    debug(L);
    return make_pair(ans, L);
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);


int N, L;
int to_int(char c) {
    if (c == 'R') return 0;
    else if (c == 'G') return 1;
    else return 2;
}

char to_char(int i) {
    const string S = "RGB";
    return S[i];
}

int base_one(int prv, int res) {
    if ((prv+1)%3 != res) return (prv+1)%3;
    else return (prv+2)%3;
}
const int maxfib = 28;
int fib[30];

}
void init(int N, int l) {
    ::N = N;
    ::L = l;
    debug("L", l);

    fib[0] = fib[1] = 1;
    for (int i = 2;i < 29;i++) fib[i] = fib[i-1] + fib[i-2]; 
}

int bruno(string s) {
    if (N == L) return 1;
    int len = s.size();
    vector<int> v;
    for (int i = 1;i < len;i++) {
        if (s[i] == s[i-1]) v.push_back(0);
        else v.push_back(1);
    }
    debug(s);
    pary(v.begin(), v.end());
    vector<int> bits, pref;
    int count = 0;
    for (int i = 0;i < v.size();i++) {
        if (v[i] == 0) {
            bits.push_back(count / 2);
            pref.push_back(i - count);
            count = 0;
        } else {
            count += 1;
        }
    }
    if (count >= 4) {
        bits.push_back(2);
        pref.push_back(v.size() - count);
    }
    pary(bits.begin(), bits.end());
    pary(pref.begin(), pref.end());
    int num = 0;
    int ind = maxfib-1;
    for (int i = 0;i < bits.size();i++) {
        if (bits[i] == 2) {
            for (int j = i+1;j < bits.size();j++) {
                if (bits[j] == 2) break;
                num += bits[j] * fib[ind];
                if (bits[j] == 1) ind -= 2;
                else ind -= 1;
            }
            debug(num);
            num -= pref[i+1];
            break;
        }
    }
    debug("Answer", num);
    return num;
}

Compilation message (stderr)

Anna.cpp: In function 'void add_bit(std::vector<int>&, std::vector<int>&, int)':
Anna.cpp:54:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     if (ind >= v.size()) return;
      |         ~~~~^~~~~~~~~~~
Anna.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if (ind >= v.size()) return;
      |             ~~~~^~~~~~~~~~~
Anna.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         if (ind+1 >= v.size()) {
      |             ~~~~~~^~~~~~~~~~~
Anna.cpp: In function 'std::pair<std::__cxx11::basic_string<char>, int> anna(int, std::string)':
Anna.cpp:84:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |     while (ret.size() < N) {
      |            ~~~~~~~~~~~^~~
Anna.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
Anna.cpp:110:5: note: in expansion of macro 'pary'
  110 |     pary(bigarr.begin(), bigarr.end());
      |     ^~~~
Anna.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
Anna.cpp:116:5: note: in expansion of macro 'debug'
  116 |     debug(L);
      |     ^~~~~
Anna.cpp: At global scope:
Anna.cpp:42:5: warning: 'int {anonymous}::diff(int, int)' defined but not used [-Wunused-function]
   42 | int diff(int a, int b) {
      |     ^~~~

Bruno.cpp: In function 'void init(int, int)':
Bruno.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
Bruno.cpp:48:5: note: in expansion of macro 'debug'
   48 |     debug("L", l);
      |     ^~~~~
Bruno.cpp: In function 'int bruno(std::string)':
Bruno.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
Bruno.cpp:62:5: note: in expansion of macro 'debug'
   62 |     debug(s);
      |     ^~~~~
Bruno.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
Bruno.cpp:63:5: note: in expansion of macro 'pary'
   63 |     pary(v.begin(), v.end());
      |     ^~~~
Bruno.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0;i < v.size();i++) {
      |                    ~~^~~~~~~~~~
Bruno.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
Bruno.cpp:79:5: note: in expansion of macro 'pary'
   79 |     pary(bits.begin(), bits.end());
      |     ^~~~
Bruno.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
Bruno.cpp:80:5: note: in expansion of macro 'pary'
   80 |     pary(pref.begin(), pref.end());
      |     ^~~~
Bruno.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0;i < bits.size();i++) {
      |                    ~~^~~~~~~~~~~~~
Bruno.cpp:85:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for (int j = i+1;j < bits.size();j++) {
      |                              ~~^~~~~~~~~~~~~
Bruno.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
Bruno.cpp:91:13: note: in expansion of macro 'debug'
   91 |             debug(num);
      |             ^~~~~
Bruno.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
Bruno.cpp:96:5: note: in expansion of macro 'debug'
   96 |     debug("Answer", num);
      |     ^~~~~
Bruno.cpp: At global scope:
Bruno.cpp:37:5: warning: 'int {anonymous}::base_one(int, int)' defined but not used [-Wunused-function]
   37 | int base_one(int prv, int res) {
      |     ^~~~~~~~
Bruno.cpp:32:6: warning: 'char {anonymous}::to_char(int)' defined but not used [-Wunused-function]
   32 | char to_char(int i) {
      |      ^~~~~~~
Bruno.cpp:26:5: warning: 'int {anonymous}::to_int(char)' defined but not used [-Wunused-function]
   26 | int to_int(char c) {
      |     ^~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 15 / 15
• Subtask 5: 9.99999 / 70