Submission #372428

#	Time	Username	Problem	Language	Result	Execution time	Memory
372428		Killer2501	Painting Squares (IOI20_squares)	C++14	100 / 100	163 ms	576 KiB

squares

#include <bits/stdc++.h>
#define pb push_back
#define vii vector<int>
#define task "ABC"
#define pll pair<ll, ll>
#define pii pair< pll, ll >
#define fi first
#define se second

using namespace std;
using ll = int;
using ull = unsigned long long;
const int N = 3e5+5;
const ll mod = 1e9+7;
const ll base1 = 1313;
const ll base2 = 3113;
string s;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}

vector<ll> paint(int n)
{
    //cin >> n;
    vector<ll> kq, a, b;
    ll lf = 1, rt = 22, mid;
    while(lf <= rt)
    {
        mid = (lf + rt) / 2;
        int tong = (1<<mid) + mid-1;
        if(tong < n)lf = mid + 1;
        else rt  = mid - 1;
    }
    int k = lf;
    a.resize(n+2);
    b.resize((1<<k)+5);
    int tong = 0;
    for(int i = 1; i <= k;  i++)
    {
        kq.pb(1);
        tong = tong * 2 + 1;
    }
    a[k] = tong;
    b[tong] = 1;
    for(int i = k+1; i <= n; i ++)
    {
        int t = a[i-1] * 2;
        t &= tong;
        if(b[t] == 0)kq.pb(0);
        else
        {
            t += 1;
            kq.pb(1);
        }
        a[i] = t;
        b[t] = 1;
    }
    kq.pb(k);
    return kq;
}
int find_location(int n, vector<int> c)
{
    vector<int> a, b;
    int k = c.size();
    int tong = 0;
    int ans = 0;
    for(int i = 0; i < k; i ++)
    {
        if(c[i] == -1)
        {
            return n-i;
        }
        if(c[i] == 1)ans = ans * 2 + 1;
        else ans = ans * 2;
        tong = tong * 2 + 1;
    }
    //cout << ans <<" "<<tong << '\n';
    a.resize(n+2);
    b.resize((1<<k)+5);
    a[k] = tong;
    if(tong == ans)
    {
        return 0;
    }
    for(int i = k+1; i <= n; i ++)
    {
        int t = a[i-1] * 2;
        t &= tong;
        if(b[t])++t;
        a[i] = t;
        b[t] = 1;
        if(a[i] == ans)
        {
            return i-k;
        }
    }

}

Compilation message (stderr)

squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:70:17: warning: control reaches end of non-void function [-Wreturn-type]
   70 |     vector<int> a, b;
      |                 ^

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55