oj.uz

Submission #1042632

# Submission time Handle Problem Language Result Execution time Memory
1042632 2024-08-03T08:50:23 Z joelgun14 Carnival (CEOI14_carnival) C++17
100 / 100
 6 ms 596 KB 
#include <bits/stdc++.h>
using namespace std;
int query(int left, int right)
{
  cout << right - left + 1 << " ";
  for(int i = left; i <= right; ++i)
    cout << i << " ";
  cout << endl;
  int input;
  cin >> input;
  return input;
}
int main()
{
    int t, n, q;
    cin >> n;
    t = 100, q = 00;
    int color[n]; color[0] = 1;
    if(t <= 2)
    {
        for(int i = 0; i < n; ++i)
            color[i] = query(1, i + 1);
    }
    else if(t <= 4)
    {
        int color_counter = 1;
        for(int i = 1; i < n; ++i)
        {
            // binser previous colors
            if(color_counter == 1)
            {
                color[i] = query(1, i + 1);
                if(color[i] > 1)
                    ++color_counter;
            }   
            else
            {
                // binser previous colors
                int left = 1, right = min(4, color_counter + 1);
                bool used[5];
                while(left < right)
                {
                    memset(used, 0, sizeof(used));
                    int mid = (left + right) / 2, cnt = 0, idx;
                    // find an index such that there is a mid amount of colors
                    for(int j = i - 1; j >= 0; --j)
                    {
                        if(!used[color[j]])
                            used[color[j]] = 1, ++cnt;
                        if(cnt == mid)
                        {
                            idx = j;
                            break;
                        }
                    }
                    if(query(idx + 1, i + 1) == mid)
                        right = mid;
                    else
                        left = mid + 1;
                }
                if(left > color_counter)
                    color[i] = ++color_counter;
                else
                {
                    // find the ith color from the current index, where i = left
                    memset(used, 0, sizeof(used));
                    int cnt = 0;
                    for(int j = i - 1; j >= 0; --j)
                    {
                        if(!used[color[j]])
                            used[color[j]] = 1, ++cnt;
                        if(cnt == left)
                        {
                            color[i] = color[j];
                            break;
                        }
                    }
                }
            }
        }
    }
    else if(t <= 5)
    {
        // use 2 pointers to find in O(n)
        if(query(1, n) == n)
        {
            for(int i = 1; i < n; ++i)
                color[i] = i + 1;
        }
        else
        {
            int prev = 0, left, right;
            for(int i = 1; i < n; ++i)
            {
                ++prev;
                if(query(1, i + 1) == prev)
                {
                    right = i;
                    break;
                }
            }
            prev = 0;
            for(int i = n - 2; i >= 0; --i)
            {
                ++prev;
                if(query(i + 1, n) == prev)
                {
                    left = i;
                    break;
                }
            }
            int cur_color = 1;
            for(int i = 0; i < n; ++i)
            {
                if(i == right)
                    color[i] = color[left];
                else
                    color[i] = cur_color++;
            }
        }
    }
    else
    {
        bool used[n + 1];
        int color_counter = 1;
        for(int i = 1; i < n; ++i)
        {
            // binser previous colors
            int left = 1, right = color_counter + 1;
            // do binser
            while(left < right)
            {
                memset(used, 0, sizeof(used));
                int mid = (left + right) / 2, cnt = 0, idx;
                for(int j = i - 1; j >= 0; --j)
                {
                    if(!used[color[j]])
                        ++cnt, used[color[j]] = 1;
                    if(cnt == mid)
                    {
                        idx = j;
                        break;
                    }
                }
                if(query(idx + 1, i + 1) == mid)
                    right = mid;
                else
                    left = mid + 1;
            }
            if(left == color_counter + 1)
                color[i] = ++color_counter;
            else
            {
                int cnt = 0;
                memset(used, 0, sizeof(used));
                for(int j = i - 1; j >= 0; --j)
                {
                    if(!used[color[j]])
                        ++cnt, used[color[j]] =  1;
                    if(cnt == left)
                    {
                        color[i] = color[j];
                        break;
                    }
                }
            }
        }
    }
    cout << "0 ";
    for(int i = 0; i < n; ++i)
        cout << color[i] << " ";
    cout << endl;
    return 0;
}

Compilation message

carnival.cpp: In function 'int main()':
carnival.cpp:15:15: warning: variable 'q' set but not used [-Wunused-but-set-variable]
   15 |     int t, n, q;
      |               ^
carnival.cpp:145:25: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  145 |                 if(query(idx + 1, i + 1) == mid)
      |                    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 4 ms 568 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 6 ms 596 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct