Submission #202845

#	Time	Username	Problem	Language	Result	Execution time	Memory
202845		MKopchev	Lollipop (POI11_liz)	C++14	100 / 100	952 ms	26808 KiB

liz

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e6+42;
int n,m;
int inp[nmax];
int take()
{
    char c;
    scanf("%c",&c);
    while(c!='T'&&c!='W')scanf("%c",&c);
    if(c=='T')return 2;
    return 1;
}

int sum[nmax];

bool only_two(int l,int r)
{
    return sum[r]-sum[l-1]==2*(r-l+1);
}

int ask(int l,int r)
{
    if(l<1||r>n)return 0;
    return sum[r]-sum[l-1];
}
void query()
{
    int want;
    scanf("%i",&want);

    if(want>sum[n])
    {
        printf("NIE\n");
        return;
    }

    int l=1;
    int r=0,not_ok=n+1;
    while(not_ok-r>1)
    {
        int av=(r+not_ok)/2;
        if(sum[av]<=want)r=av;
        else not_ok=av;
    }

    if(sum[r]==want)
    {
        printf("%i %i\n",l,r);
        return;
    }

    int ok_add=0,not_ok_add=n-r+1;
    while(not_ok_add-ok_add>1)
    {
        int av=(not_ok_add+ok_add)/2;
        if(only_two(l,av)&&only_two(r+1,r+av))ok_add=av;
        else not_ok_add=av;
    }

    l=l+ok_add;
    r=r+ok_add;

    for(int l_add=-1;l_add<=1;l_add++)
        for(int r_add=-1;r_add<=1;r_add++)
        {
            int l_now=l+l_add;
            int r_now=r+r_add;

            if(ask(l_now,r_now)==want)
            {
                printf("%i %i\n",l_now,r_now);
                return;
            }
        }
    printf("NIE\n");
}
int main()
{
    scanf("%i%i",&n,&m);
    for(int i=1;i<=n;i++)inp[i]=take();

    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+inp[i];

    for(int i=1;i<=m;i++)
        query();

    return 0;
}

Compilation message (stderr)

liz.cpp: In function 'int take()':
liz.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%c",&c);
     ~~~~~^~~~~~~~~
liz.cpp:10:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     while(c!='T'&&c!='W')scanf("%c",&c);
                          ~~~~~^~~~~~~~~
liz.cpp: In function 'void query()':
liz.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&want);
     ~~~~~^~~~~~~~~~~~
liz.cpp: In function 'int main()':
liz.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&m);
     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9