oj.uz

Submission #654624

# Submission time Handle Problem Language Result Execution time Memory
654624 2022-11-01T02:40:09 Z Tuanlinh123 Library (JOI18_library) C++17
100 / 100
 358 ms 576 KB 
#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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 208 KB # of queries: 2730
2 Correct 54 ms 328 KB # of queries: 2798
3 Correct 26 ms 332 KB # of queries: 2864
4 Correct 36 ms 208 KB # of queries: 2898
5 Correct 41 ms 324 KB # of queries: 2884
6 Correct 40 ms 324 KB # of queries: 2850
7 Correct 33 ms 208 KB # of queries: 2940
8 Correct 33 ms 324 KB # of queries: 2796
9 Correct 43 ms 316 KB # of queries: 2930
10 Correct 21 ms 208 KB # of queries: 1712
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 2
13 Correct 1 ms 208 KB # of queries: 6
14 Correct 1 ms 208 KB # of queries: 12
15 Correct 1 ms 208 KB # of queries: 98
16 Correct 3 ms 208 KB # of queries: 230

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 208 KB # of queries: 2730
2 Correct 54 ms 328 KB # of queries: 2798
3 Correct 26 ms 332 KB # of queries: 2864
4 Correct 36 ms 208 KB # of queries: 2898
5 Correct 41 ms 324 KB # of queries: 2884
6 Correct 40 ms 324 KB # of queries: 2850
7 Correct 33 ms 208 KB # of queries: 2940
8 Correct 33 ms 324 KB # of queries: 2796
9 Correct 43 ms 316 KB # of queries: 2930
10 Correct 21 ms 208 KB # of queries: 1712
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 2
13 Correct 1 ms 208 KB # of queries: 6
14 Correct 1 ms 208 KB # of queries: 12
15 Correct 1 ms 208 KB # of queries: 98
16 Correct 3 ms 208 KB # of queries: 230
17 Correct 287 ms 444 KB # of queries: 19364
18 Correct 283 ms 464 KB # of queries: 19016
19 Correct 292 ms 448 KB # of queries: 19160
20 Correct 252 ms 328 KB # of queries: 17832
21 Correct 202 ms 320 KB # of queries: 16854
22 Correct 327 ms 576 KB # of queries: 19274
23 Correct 358 ms 324 KB # of queries: 19252
24 Correct 120 ms 320 KB # of queries: 8846
25 Correct 314 ms 480 KB # of queries: 18830
26 Correct 229 ms 324 KB # of queries: 17506
27 Correct 126 ms 312 KB # of queries: 8832
28 Correct 289 ms 328 KB # of queries: 17954
29 Correct 267 ms 336 KB # of queries: 17934
30 Correct 263 ms 452 KB # of queries: 17954