Submission #654624

#	Time	Username	Problem	Language	Result	Execution time	Memory
654624		Tuanlinh123	Library (JOI18_library)	C++17	100 / 100	358 ms	576 KiB

library

#include "library.h"
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/"
#define maxn 1005

ll n;
vector <ll> ans[maxn];

ll calc(ll idx, ll l, ll r)
{
    ll q1=0, q2=0;
    vector <ll> m;
    m.assign(n, 0);
    for (ll i=l; i<=r; i++)
        m[i-1]=1;
    q1=Query(m);
    m[idx-1]=1;
    q2=Query(m);
    return q1+1-q2;
}

ll Find(ll idx, ll l, ll r, ll num)
{
    if (r<l)
        return 0;
    ll mid=(l+r)/2, q=(num==-1 ? calc(idx, l, r) : num);
    if (q==0)
        return q;
    if (l==r && q==1)
    {
        ans[idx].pb(l);
        return q;
    }
    ll q1=Find(idx, l, mid, -1);
    Find(idx, mid+1, r, q-q1);
    return q;
}

ll findstart()
{
    for (ll i=1; i<=n; i++)
        if (ans[i].size()==1)
            return i;
	return 0;
}

ll findnext(ll idx, ll prev)
{
    for (ll i=0; i<ans[idx].size(); i++)
        if (ans[idx][i]!=prev)
            return ans[idx][i];
    return -1;
}

void Solve(ll N)
{
    srand((ll)time(0));
	if (N==1)
	{
		vector <ll> res;
		res.pb(1);
		Answer(res);
		return;
	}
    n=N;
    for (ll i=1; i<=n; i++)
        Find(i, 1, i-1, -1);
    for (ll i=1; i<=n; i++)
        for (ll j:ans[i])
            ans[j].pb(i);
    vector <ll> res;
    ll st=findstart();
    while (st!=-1)
    {
        res.pb(st);
        st=findnext(st, (res.size()==1 ? 0 : res[res.size()-2]));
    }
    Answer(res);
}

Compilation message (stderr)

library.cpp: In function 'int findstart()':
library.cpp:51:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   51 |     for (ll i=1; i<=n; i++)
      |     ^~~
library.cpp:54:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   54 |  return 0;
      |  ^~~~~~
library.cpp: In function 'int findnext(int, int)':
library.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (ll i=0; i<ans[idx].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81