oj.uz

Submission #260373

# Submission time Handle Problem Language Result Execution time Memory
260373 2020-08-10T07:42:48 Z 최은수(#5043) Library (JOI18_library) C++17
100 / 100
 335 ms 6520 KB 
#include"library.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
int n;
int ct=0;
int query(vector<int>v)
{
    vector<int>m(n,0);
    for(int&t:v)
        m[t-1]=1;
    return Query(m);
}
int qu(int i,int j)
{
    return query(vector<int>({i,j}));
}
int ivq[2010][2010];
int iq(int s,int e)
{
    if(s==e)
        return 1;
    if(ivq[s][e]!=0)
        return ivq[s][e];
    vector<int>qv;
    for(int i=s;i<=e;i++)
        qv.eb(i);
    return ivq[s][e]=query(qv);
}
vector<int>adj[2010];
void solv2(int l,int s,int e,int c)
{
    if(c==0)
        return;
    if(s==e)
    {
        adj[l].eb(s);
        adj[s].eb(l);
        return;
    }
    int m=s+(e-s)/2;
    int lc;
    {
        vector<int>qv;
        for(int i=s;i<=m;i++)
            qv.eb(i);
        qv.eb(l);
        lc=ivq[s][m]+1-query(qv);
    }
    solv2(l,s,m,lc);
    solv2(l,m+1,e,c-lc);
    return;
}
void solv(int l,int r,int s,int e,int c)
{
    if(c==0)
        return;
    if(l==r)
        return solv2(l,s,e,c);
    int m=l+(r-l)/2;
    int lc;
    {
        vector<int>qv;
        for(int i=l;i<=m;i++)
            qv.eb(i);
        for(int i=s;i<=e;i++)
            qv.eb(i);
        lc=ivq[l][m]+ivq[s][e]-query(qv);
    }
    solv(l,m,s,e,lc);
    solv(m+1,r,s,e,c-lc);
    return;
}
void solve(int s,int e,int cur)
{
    if(cur==e-s+1)
    {
        for(int i=s;i<=e;i++)
            for(int j=i;j<=e;j++)
                ivq[i][j]=j-i+1;
        return;
    }
    int m=s+(e-s)/2; //[s,m], [m+1,e]
    solve(s,m,iq(s,m));
    solve(m+1,e,iq(m+1,e));
    if(ivq[s][m]+ivq[m+1][e]!=cur)
        solv(s,m,m+1,e,ivq[s][m]+ivq[m+1][e]-cur);
    for(int i=m;i>=s;i--)
    {
        for(int j=m,c=0;j++<e;)
        {
            for(int&t:adj[j])
                if(i<=t&&t<=m)
                    c++;
            ivq[i][j]=ivq[i][m]+ivq[m+1][j]-c;
        }
    }
    return;
}
void Solve(int N)
{
    n=N;
    if(n==1)
        return Answer({1});
    ivq[1][n]=1;
    solve(1,n,1);
    int x=0,p=0;
    for(int i=0;i++<n;)
        if((int)adj[i].size()==1)
            x=i;
    vector<int>ans;
    while((int)ans.size()<n)
    {
        ans.eb(x);
        int nx=0;
        for(int&t:adj[x])
            if(t!=p)
                nx=t;
        p=x;
        x=nx;
    }
    Answer(ans);
    return;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1200 KB # of queries: 1359
2 Correct 23 ms 1152 KB # of queries: 1382
3 Correct 31 ms 1264 KB # of queries: 1404
4 Correct 25 ms 1272 KB # of queries: 1448
5 Correct 33 ms 1272 KB # of queries: 1422
6 Correct 25 ms 1272 KB # of queries: 1440
7 Correct 26 ms 1272 KB # of queries: 1440
8 Correct 18 ms 1196 KB # of queries: 1387
9 Correct 24 ms 1272 KB # of queries: 1432
10 Correct 13 ms 896 KB # of queries: 837
11 Correct 0 ms 384 KB # of queries: 0
12 Correct 0 ms 384 KB # of queries: 0
13 Correct 0 ms 384 KB # of queries: 2
14 Correct 1 ms 384 KB # of queries: 5
15 Correct 2 ms 384 KB # of queries: 49
16 Correct 3 ms 512 KB # of queries: 117

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1200 KB # of queries: 1359
2 Correct 23 ms 1152 KB # of queries: 1382
3 Correct 31 ms 1264 KB # of queries: 1404
4 Correct 25 ms 1272 KB # of queries: 1448
5 Correct 33 ms 1272 KB # of queries: 1422
6 Correct 25 ms 1272 KB # of queries: 1440
7 Correct 26 ms 1272 KB # of queries: 1440
8 Correct 18 ms 1196 KB # of queries: 1387
9 Correct 24 ms 1272 KB # of queries: 1432
10 Correct 13 ms 896 KB # of queries: 837
11 Correct 0 ms 384 KB # of queries: 0
12 Correct 0 ms 384 KB # of queries: 0
13 Correct 0 ms 384 KB # of queries: 2
14 Correct 1 ms 384 KB # of queries: 5
15 Correct 2 ms 384 KB # of queries: 49
16 Correct 3 ms 512 KB # of queries: 117
17 Correct 254 ms 6392 KB # of queries: 9380
18 Correct 283 ms 6392 KB # of queries: 9288
19 Correct 326 ms 6392 KB # of queries: 9320
20 Correct 259 ms 6008 KB # of queries: 8777
21 Correct 241 ms 5624 KB # of queries: 8312
22 Correct 326 ms 6392 KB # of queries: 9377
23 Correct 335 ms 6392 KB # of queries: 9336
24 Correct 109 ms 3008 KB # of queries: 4287
25 Correct 314 ms 6264 KB # of queries: 9165
26 Correct 249 ms 5932 KB # of queries: 8547
27 Correct 87 ms 2936 KB # of queries: 4308
28 Correct 119 ms 6328 KB # of queries: 2977
29 Correct 107 ms 6520 KB # of queries: 2974
30 Correct 96 ms 6392 KB # of queries: 2977