답안 #45954 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45954	2018-04-16T14:28:47 Z	bogdan10bos	도서관 (JOI18_library)	C++14	100 / 100	371 ms	5324 KB

library

#include <bits/stdc++.h>

using namespace std;

//#define DEBUG

#ifndef DEBUG
#include "library.h"
#endif // DEBUG

#ifdef DEBUG
int Query(const vector<int>& M);
void Answer(const vector<int>& res);
#endif


typedef pair<int, int> pii;

map<pii, int> mp;
int _N;

int ask(vector<int> v)
{
    int N = _N;
    vector<int> f;
    f.resize(N);
    for(int i = 1; i <= N; i++)
        f[i - 1] = 0;
    for(auto x: v)
        f[x - 1] = 1;
    int ans = Query(f);
    ans = v.size() - ans;
    return ans;
}

int ask(int st, int dr)
{
    if(mp.count({st, dr}))  return mp[{st, dr}];
    vector<int> v;
    for(int i = st; i <= dr; i++)
        v.push_back(i);
    int ans = ask(v);
    mp[{st, dr}] = ans;
    return ans;
}


class BinaryIndexedTree2D
{
public:

    int N;
    int aib[1005][1005];

    void init(int _N)
    {
        N = _N;
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                aib[i][j] = 0;
    }

    void U(int x, int y, int v)
    {
        for(int i = x; i <= N; i += (i & (-i)))
            for(int j = y; j <= N; j += (j & (-j)))
                aib[i][j] += v;
    }

    void U(int xs, int ys, int xf, int yf, int val)
    {
        U(xs, ys, val);
        U(xs, yf + 1, -val);
        U(xf + 1, ys, -val);
        U(xf + 1, yf + 1, val);
    }

    int Q(int x, int y)
    {
        int ans = 0;
        for(int i = x; i > 0; i -= (i & (-i)))
            for(int j = y; j > 0; j -= (j & (-j)))
                ans += aib[i][j];
        return ans;
    }
}aib;

void Solve(int N)
{
    if(N == 1)
    {
        vector<int> ans;
        ans.push_back(1);
        Answer(ans);
        return;
    }

    _N = N;
    aib.init(N); mp.clear();
    vector<int> edg[1005];
    for(int i = 1; i <= N; i++) edg[i].clear();

    int pfx[1005];

    vector<int> val;
    pfx[1] = 0;
    val.push_back(1);
    for(int i = 2; i <= N; i++)
    {
        val.push_back(i);
        pfx[i] = ask(val);
    }
    for(int i = 2; i <= N; i++)
    {
        for(int j = 1; j <= pfx[i] - pfx[i - 1]; j++)
        {
            int p = 1;
            int u = i - 1;
            int x = 0;
            while(p <= u)
            {
                int mij = p + (u - p) / 2;
                int val = ask(mij, i);
                if(val - aib.Q(mij, i) >= 1)
                {
                    x = mij;
                    p = mij + 1;
                }
                else
                    u = mij - 1;
            }
            edg[x].push_back(i);
            edg[i].push_back(x);
            aib.U(1, i, x, N, 1);
        }
    }

    vector<int> ans;
    for(int i = 1; i <= N; i++)
        if(edg[i].size() == 1)
        {
            ans.push_back(i);
            ans.push_back(edg[i][0]);
            break;
        }
    for(int i = 3; i <= N; i++)
    {
        int x = ans[i - 2];
        int y = ans[i - 3];
        int nxt = y ^ edg[x][0] ^ edg[x][1];
        ans.push_back(nxt);
    }
    Answer(ans);

}

#ifdef DEBUG

namespace {
struct Judge
{
	int N;
	int A[1002];
	int pos[1002];
	bool f[1002];
	int query_c;
	bool answered;
	void init()
	{
	    freopen("1.in", "r", stdin);
		query_c=0;
		int ret=scanf("%d",&N); ret++;
		answered=false;
		for(int i=0;i<N;i++)ret=scanf("%d",&A[i]),pos[A[i]]=i;
	}
	int query(const vector<int>& M)
	{
		if(query_c==20000)
		{
			puts("Wrong Answer [3]");
			exit(0);
		}
		if(int(M.size())!=N)
		{
			puts("Wrong Answer [1]");
			exit(0);
		}
		bool all_zero=true;
		for(int i=0;i<N;i++)
		{
			if(M[i]!=0&&M[i]!=1)
			{
				puts("Wrong Answer [2]");
				exit(0);
			}
			if(M[i]==1)all_zero=false;
		}
		if(all_zero)
		{
			puts("Wrong Answer [2]");
			exit(0);
		}
		memset(f,0,sizeof(f));
		for(int i=0;i<N;i++)if(M[i])f[pos[i+1]]=true;
		bool las=false;
		int r=0;
		for(int i=0;i<N;i++)
		{
			if(las==false&&f[i]==true)r++;
			las=f[i];
		}
		query_c++;
		return r;
	}
	void answer(const vector<int>& res)
	{
		bool f1=true,f2=true;
		if(int(res.size())!=N)
		{
			puts("Wrong Answer [4]");
			exit(0);
		}
		if(answered)
		{
			puts("Wrong Answer [7]");
			exit(0);
		}
		answered=true;
		memset(f,0,sizeof(f));
		for(int i=0;i<N;i++)
		{
			if(res[i]<=0||res[i]>N)
			{
				puts("Wrong Answer [5]");
				exit(0);
			}
			if(f[res[i]])
			{
				puts("Wrong Answer [6]");
				exit(0);
			}
			f[res[i]]=true;
		}
		for(int i=0;i<N;i++)
		{
			f1&=A[i]==res[i];
			f2&=A[i]==res[N-i-1];
		}
		if(!f1&&!f2)
		{
			puts("Wrong Answer [8]");
			exit(0);
		}
	}
	void end()
	{
		if(!answered)puts("Wrong Answer [7]");
		else printf("Accepted : %d\n",query_c);
	}
}judge;
}

int Query(const vector<int>& M)
{
	return judge.query(M);
}
void Answer(const vector<int>& res)
{
	judge.answer(res);
}

int main()
{
	judge.init();
	Solve(judge.N);
	judge.end();
}
#endif

Subtask #1
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	1084 KB	Output is correct
2	Correct	23 ms	1204 KB	Output is correct
3	Correct	24 ms	1412 KB	Output is correct
4	Correct	25 ms	1412 KB	Output is correct
5	Correct	23 ms	1412 KB	Output is correct
6	Correct	26 ms	1412 KB	Output is correct
7	Correct	32 ms	1412 KB	Output is correct
8	Correct	23 ms	1412 KB	Output is correct
9	Correct	32 ms	1440 KB	Output is correct
10	Correct	15 ms	1440 KB	Output is correct
11	Correct	2 ms	1440 KB	Output is correct
12	Correct	2 ms	1440 KB	Output is correct
13	Correct	2 ms	1440 KB	Output is correct
14	Correct	2 ms	1440 KB	Output is correct
15	Correct	2 ms	1440 KB	Output is correct
16	Correct	3 ms	1440 KB	Output is correct

Subtask #2
81.0 / 81.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	1084 KB	Output is correct
2	Correct	23 ms	1204 KB	Output is correct
3	Correct	24 ms	1412 KB	Output is correct
4	Correct	25 ms	1412 KB	Output is correct
5	Correct	23 ms	1412 KB	Output is correct
6	Correct	26 ms	1412 KB	Output is correct
7	Correct	32 ms	1412 KB	Output is correct
8	Correct	23 ms	1412 KB	Output is correct
9	Correct	32 ms	1440 KB	Output is correct
10	Correct	15 ms	1440 KB	Output is correct
11	Correct	2 ms	1440 KB	Output is correct
12	Correct	2 ms	1440 KB	Output is correct
13	Correct	2 ms	1440 KB	Output is correct
14	Correct	2 ms	1440 KB	Output is correct
15	Correct	2 ms	1440 KB	Output is correct
16	Correct	3 ms	1440 KB	Output is correct
17	Correct	330 ms	5104 KB	Output is correct
18	Correct	315 ms	5196 KB	Output is correct
19	Correct	329 ms	5196 KB	Output is correct
20	Correct	251 ms	5196 KB	Output is correct
21	Correct	284 ms	5196 KB	Output is correct
22	Correct	318 ms	5324 KB	Output is correct
23	Correct	371 ms	5324 KB	Output is correct
24	Correct	123 ms	5324 KB	Output is correct
25	Correct	292 ms	5324 KB	Output is correct
26	Correct	290 ms	5324 KB	Output is correct
27	Correct	110 ms	5324 KB	Output is correct
28	Correct	309 ms	5324 KB	Output is correct
29	Correct	324 ms	5324 KB	Output is correct
30	Correct	297 ms	5324 KB	Output is correct

답안 #45954

Compilation message

Subtask #1 19.0 / 19.0

Subtask #2 81.0 / 81.0

Subtask #1
19.0 / 19.0

Subtask #2
81.0 / 81.0