oj.uz

Submission #202845

# Submission time Handle Problem Language Result Execution time Memory
202845 2020-02-18T08:10:31 Z MKopchev Lollipop (POI11_liz) C++14
100 / 100
 952 ms 26808 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 14 ms 632 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Output is correct
2 Correct 10 ms 504 KB Output is correct
3 Correct 10 ms 504 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 888 KB Output is correct
2 Correct 15 ms 760 KB Output is correct
3 Correct 59 ms 1912 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1912 KB Output is correct
2 Correct 209 ms 6196 KB Output is correct
3 Correct 116 ms 3704 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1912 KB Output is correct
2 Correct 50 ms 2296 KB Output is correct
3 Correct 135 ms 4216 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 5624 KB Output is correct
2 Correct 159 ms 5368 KB Output is correct
3 Correct 284 ms 8184 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 12408 KB Output is correct
2 Correct 384 ms 12024 KB Output is correct
3 Correct 556 ms 15736 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 12664 KB Output is correct
2 Correct 454 ms 15480 KB Output is correct
3 Correct 697 ms 18936 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 890 ms 25680 KB Output is correct
2 Correct 643 ms 24440 KB Output is correct
3 Correct 952 ms 25080 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 25464 KB Output is correct
2 Correct 763 ms 25208 KB Output is correct
3 Correct 663 ms 26808 KB Output is correct