Submission #255345

#	Time	Username	Problem	Language	Result	Execution time	Memory
255345		uacoder123	Xylophone (JOI18_xylophone)	C++14	100 / 100	134 ms	1032 KiB

xylophone

#include <cstdio>
#include <cstdlib>
#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;

void solve(int N) 
{
  int n=N;
  int arr[n],arr1[n];
  for(int i=1;i<n;++i)
    arr[i]=query(i,i+1);
  for(int i=1;i<n-1;++i)
    arr1[i]=query(i,i+2);
  int l=1,l1=0,mi=0,mi1=0;
  int arr2[n+1],arr3[n+1];
  arr2[1]=0;
  arr2[2]=arr[1];
  arr3[1]=0;
  arr3[2]=-arr[1];
  for(int i=2;i<n;++i)
  {
    if(arr1[i-1]!=arr[i-1]+arr[i])
    {
      if(l==1)
        arr2[i+1]=arr2[i]-arr[i];
      else
        arr2[i+1]=arr2[i]+arr[i];
      l^=1;
    }
    else
    {
    if(l==1)
        arr2[i+1]=arr2[i]+arr[i];
      else
        arr2[i+1]=arr2[i]-arr[i]; 
    }
    if(arr1[i-1]!=arr[i-1]+arr[i])
    {
      if(l1==1)
        arr3[i+1]=arr3[i]-arr[i];
      else
        arr3[i+1]=arr3[i]+arr[i];
      l1^=1;
    }
    else
    {
    if(l1==1)
        arr3[i+1]=arr3[i]+arr[i];
      else
        arr3[i+1]=arr3[i]-arr[i]; 
    }
  }
  for(int i=1;i<=n;++i)
  {
    mi=min(mi,arr2[i]);
    mi1=min(mi1,arr3[i]);
  }
  mi=-mi;
  mi1=-mi1;
  mi++;
  mi1++;
  ii f,s;
  int ch=1,ch1=1;
  set<int> se,se1;
  for(int i=1;i<=n;++i)
  {
    arr2[i]+=mi;
    se.insert(arr2[i]);
    arr3[i]+=mi1;
    se1.insert(arr3[i]);
    if(arr2[i]==1)
      f.F=i;
    else if(arr2[i]==n)
      f.S=i;
    if(arr3[i]==1)
      s.F=i;
    else if(arr3[i]==n)
      s.S=i;
  }
  if(se.size()!=n||(*(--se.end()))!=n)
    ch=0;
  if(se1.size()!=n||(*(--se1.end()))!=n)
    ch1=0;
  if(ch==1&&ch1==1)
  {
    if(f.F==s.F)
    {
      int r;
      if(s.S>=f.S)
      {
        r=query(min(f.F,f.S),max(f.F,f.S));
        if(r==n-1)
          ch1=0;
        else
          ch=0;
      }
      else
      {
      r=query(min(s.F,s.S),max(s.F,s.S));
        if(r==n-1)
          ch=0;
        else
          ch1=0;  
      }
    }
    else
    {
      int r=query(min(max(f,s).F,max(f,s).S),max(max(f,s).F,max(f,s).S));
      if(max(f,s)==f)
      {
        if(r==n-1)
          ch1=0;
        else
          ch=0;
      }
      else
      {
      if(r==n-1)
          ch=0;
        else
          ch1=0;  
      }
    }
  }
  if(ch==0)
  {
    for(int i=1;i<=n;++i)
      answer(i,arr2[i]);
  }
  else
  {
  for(int i=1;i<=n;++i)
      answer(i,arr3[i]);  
  }
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:95:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(se.size()!=n||(*(--se.end()))!=n)
      ~~~~~~~~~^~~
xylophone.cpp:97:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(se1.size()!=n||(*(--se1.end()))!=n)
      ~~~~~~~~~~^~~

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