Submission #566077

#	Time	Username	Problem	Language	Result	Execution time	Memory
566077		Dodo	Xylophone (JOI18_xylophone)	C++14	100 / 100	100 ms	1132 KiB

xylophone

#include <bits/stdc++.h>
#define ll long long
//#define endl '\n'
#define pb push_back
using namespace std;
const ll mx=100006;

#include "xylophone.h"
static int A[5000];

void solve(int n) {

  map<pair<int,int>,int>mp;
  for(int i=1;i<=n;i++)
  {
    if(i+1<=n)
      mp[{i,i+1}]=query(i, i+1);
    if(i+2<=n)
      mp[{i,i+2}]=query(i, i+2);
  }

  ll sa[n+1],sb[n+1];
  deque<bool>v;
  bool m=false;
  v.push_back(m);

	for(int i = 1; i <= n-2; i++)
  {
    int c=mp[{i,i+2}],x=mp[{i,i+1}],y=mp[{i+1,i+2}];
    if(c!=x+y)
    {
      if(m)m=0;
      else m=1;
    }
    v.push_back(m);
	}
  sa[1]=1;
  sb[1]=1;
  ll mna=1,mnb=1;
  for(int i=2;i<=n;i++)
  {
    if(v.front())
    {
      sa[i]=sa[i-1]+mp[{i-1,i}];
      sb[i]=sb[i-1]-mp[{i-1,i}];
    }
    else
    {
      sa[i]=sa[i-1]-mp[{i-1,i}];
      sb[i]=sb[i-1]+mp[{i-1,i}];
    }
    mna=min(mna,sa[i]);
    mnb=min(mnb,sb[i]);
    v.pop_front();
  }

  ll x=1-mna,y=1-mnb,z=-1;
  for(int i=1;i<=n;i++)
  {
    sa[i]+=x;
    sb[i]+=y;
    if(sa[i]==1&&z==-1)z=1;
    if(sb[i]==1&&z==-1)z=0;
  }
  for(int i=1;i<=n;i++)
  {
    if(z)
    answer(i, sa[i]);
    else
    answer(i, sb[i]);
  }

}

Compilation message (stderr)

xylophone.cpp:9:12: warning: 'A' defined but not used [-Wunused-variable]
    9 | static int A[5000];
      |            ^

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