Submission #302885

#	Time	Username	Problem	Language	Result	Execution time	Memory
302885		iliccmarko	Xylophone (JOI18_xylophone)	C++14	0 / 100	1 ms	256 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"

using namespace std;

int used[5005];
int a[5005];

void solve(int n)
{
   int l = 1;
   int r = n-1;
   int start;
   while(l<=r)
   {
      int mid = (l+r)/2;
      int s = query(mid, n);
      if(s==n-1)
      {
          start = mid;
          l = mid + 1;
      }
      else
      {
          r = mid - 1;
      }
   }
   a[start] = 1;
   used[1] = start;
   if(start-1)
   {
       int k = 1 + query(start-1, start);
       a[start-1] = k;
       used[k] = start - 1; 
   }
   if(start+1<=n)
   {
       int k = 1 + query(start, start+1);
       a[start+1] = k;
       used[k] = start + 1;
   }
   for(int i = start-2;i;i--)
   {
       int s = query(i, i + 1);
       int m1, m2;
       m1 = a[i+1] + s;
       m2 = a[i+1] - s;
       if(m1>n)
       {
           used[m2] = i;
           a[i] = m2;
           continue;
       }
       if(m2<=0)
       {
           used[m1] = i;
           a[i] = m1;
           continue;
       }
       if(used[m1])
       {
           a[i] = m2;
           used[m2] = i;
           continue;
       }
       if(used[m2])
       {
           a[i] = m1;
           used[m1] = i;
           continue;
       }
       int ss = query(i, i + 2);
       if((max(a[i+2], min(m1,a[i+1])) - min(a[i+1], min(m1, a[i+2]))) == ss)
       {
           a[i] = m1;
           used[m1] = i;
       }
       else
       {
           a[i] = m2;
           used[m2] = i;
       }
   }
   for(int i = start+2;i<=n;i++)
   {
       int s = query(i-1, i);
       int m1, m2;
       m1 = a[i-1] + s;
       m2 = a[i-1] - s;
       if(m1>n)
       {
           used[m2] = i;
           a[i] = m2;
           continue;
       }
       if(m2<=0)
       {
           used[m1] = i;
           a[i] = m1;
           continue;
       }
       if(used[m1])
       {
           a[i] = m2;
           used[m2] = i;
           continue;
       }
       if(used[m2])
       {
           a[i] = m1;
           used[m1] = i;
           continue;
       }
       int ss = query(i-2, i);
       if((max(a[i-2], max(m1, a[i-1])) - min(a[i-2], min(a[i-1], m1))) == ss)
       {
           a[i] = m1;
           used[m1] = i;
       }
       else
       {
           a[i] = m2;
           used[m2] = i;
       }
   }
   for(int i = 1;i<=n;i++)
   {
       answer(i, a[i]);
   }
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:39:4: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |    if(start+1<=n)
      |    ^~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53