Submission #1050512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050512		sofijavelkovska	Stranded Far From Home (BOI22_island)	C++17	0 / 100	1091 ms	6372 KiB

island

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

const int MAXN=2e5;

int n, m;
int a[MAXN];
long long prefix[MAXN];

bool compare(int x, int y)
{
    return a[x]>a[y];
}

long long sum(int l, int r)
{
    if (l==0)
        return prefix[r];

    return prefix[r]-prefix[l-1];
}

vector<bool> brute()
{
    vector<bool> possible(n, 0);
    for (int i=0; i<n; i++)
    {
        long long sum=a[i];
        int l=i, r=i;
        while (true)
        {
            if (l>0 && sum>=a[l-1])
            {
                sum=sum+a[l-1];
                l=l-1;
            }
            else if (r<n-1 && sum>=a[r+1])
            {
                sum=sum+a[r+1];
                r=r+1;
            }
            else
                break;
        }
        if (l==0 && r==n-1)
            possible[i]=true;
    }

    return possible;
}

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);

    cin >> n >> m;
    for (int i=0; i<n; i++)
        cin >> a[i];
    for (int i=0; i<m; i++)
    {
        int x, y;
        cin >> x >> y;
    }
    auto br=brute();
    for (int i=0; i<n; i++)
        cout << br[i];
    return 0;

    srand(time(0));
    int tc=0;
    //cin >> tc;
    while (true)
    {
        tc=tc+1;
        cout << "tc " << tc << '\n';
        n=rand()%20+1, m=0;
        for (int i=0; i<n; i++)
            a[i]=rand()%20+1;
        //for (int i=0; i<n; i++)
          //  cout << a[i] << ' ';
        //cout << '\n';

    //cin >> n >> m;
    //for (int i=0; i<n; i++)
      //  cin >> a[i];
    for (int i=0; i<m; i++)
    {
        int x, y;
        cin >> x >> y;
    }
    int sorted[n];
    for (int i=0; i<n; i++)
        sorted[i]=i;
    sort(sorted, sorted+n, compare);
    int possible[n]={false};
    possible[sorted[0]]=true;
    set<int> larger;
    larger.insert(sorted[0]);
    prefix[0]=a[0];
    for (int i=1; i<=n; i++)
        prefix[i]=prefix[i-1]+a[i];
    for (int i=1; i<n; i++)
    {
        int x=sorted[i];
        int l=-1, r=n;
        auto it=larger.lower_bound(x);
        if (it!=larger.end())
            r=*it;
        if (it!=larger.begin())
        {
            it--;
            l=*it;
        }
        if (l!=-1 && possible[l] && sum(l+1, r-1)>=a[l])
            possible[x]=true;
        if (r!=n && possible[r] && sum(l+1, r-1)>=a[r])
            possible[x]=true;
        larger.insert(x);
    }

        auto br=brute();
        bool flop=false;
        for (int i=0; i<n; i++)
            if (possible[i]!=br[i])
                flop=true;
        if (flop)
        {
            cout << "FLOP\n";
            cout << n << '\n';
            for (int i=0; i<n; i++)
                cout << a[i] << ' ';
            cout << '\n';
            for (int i=0; i<n; i++)
                cout << possible[i];
            cout << '\n';
            for (int i=0; i<n; i++)
                cout << br[i];
            cout << '\n';
            break;
        }
        cout << '\n' << '\n';
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35