Submission #223425

#	Time	Username	Problem	Language	Result	Execution time	Memory
223425		maomao90	Grudanje (COCI19_grudanje)	C++14	70 / 70	66 ms	3960 KiB

grudanje

#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

typedef pair <int, int> ii;

//#define DEBUG

char letters[100005];
int N, Q;
ii subwords[100005];
vector <int> tempa, tempb, a, b;
int timeThrown[100005];
int occ[30];
int ans;

bool isValid(int time)
{
    int left = a[0], right = a[0];
    memset(occ, 0, sizeof occ);
    for (int i = 0; i < a.size(); i++)
    {
        while (left < a[i])
        {
            if (time < timeThrown[left])
            {
                occ[letters[left] - 'a']--;
            }
            left++;
        }
        while (right <= b[i])
        {
            if (time < timeThrown[right])
            {
                if (++occ[letters[right] - 'a'] > 1) return false;
            }
            right++;
        }
    }
    return true;
}

int main()
{
    scanf(" %s", letters);
    N = strlen(letters);
    for (int i = N - 1; i >= 0; i--)
    {
        letters[i + 1] = letters[i];
    }
    letters[0] = '0';
    scanf("%d", &Q);
    for (int i = 0; i < Q; i++)
    {
        int ta, tb; scanf("%d%d", &ta, &tb);
        subwords[i] = ii(ta, tb);
    }
    sort(subwords, subwords + Q);
    int prev = subwords[0].first;
    for (int i = 0; i < Q; i++)
    {
        if (subwords[i].first != prev)
        {
            tempa.push_back(subwords[i - 1].first);
            tempb.push_back(subwords[i - 1].second);
        }
        prev = subwords[i].first;
    }
    tempa.push_back(subwords[Q - 1].first);
    tempb.push_back(subwords[Q - 1].second);

    prev = tempb[0];
    for (int i = 0; i < tempa.size(); i++)
    {
        if (tempb[i] <= prev && i != 0)
        {
            continue;
        }
        else
        {
            a.push_back(tempa[i]), b.push_back(tempb[i]);
            prev = tempb[i];
        }
    }

    #ifdef DEBUG
    printf("a and b:\n");
    for (int i = 0; i < a.size(); i++)
    {
        printf("%d %d\n", a[i], b[i]);
    }
    printf("\n");
    #endif // DEBUG

    for (int i = 1; i <= N; i++)
    {
        int p; scanf("%d", &p);
        timeThrown[p] = i;
    }
    int lo = 0, hi = N, mid;
    while (lo <= hi)
    {
        mid = (lo + hi) / 2;
        if (isValid(mid))
        {
            hi = mid - 1;
            ans = mid;
        }
        else
        {
            lo = mid + 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

grudanje.cpp: In function 'bool isValid(int)':
grudanje.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); i++)
                     ~~^~~~~~~~~~
grudanje.cpp: In function 'int main()':
grudanje.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < tempa.size(); i++)
                     ~~^~~~~~~~~~~~~~
grudanje.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", letters);
     ~~~~~^~~~~~~~~~~~~~~~
grudanje.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
grudanje.cpp:59:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int ta, tb; scanf("%d%d", &ta, &tb);
                     ~~~~~^~~~~~~~~~~~~~~~~~
grudanje.cpp:101:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int p; scanf("%d", &p);
                ~~~~~^~~~~~~~~~

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