Submission #285058

#	Time	Username	Problem	Language	Result	Execution time	Memory
285058		Coroian_David	도서관 (JOI18_library)	C++11	100 / 100	354 ms	512 KiB

library

#include <bits/stdc++.h>

#define MAX_N 1000

//#include "library.h"

using namespace std;

int Query(const std::vector<int>& M);
void Answer(const std::vector<int>& res);

int n;
vector <int> tmp;
vector <int> rez;

int done[MAX_N + 1];

void divide(int st, int dr, int poz)
{
    //cout << " SUNTEM " << st << " " << dr << " " << poz << "\n";

    if(st == dr)
    {
        done[st - 1] = 1;
        rez[poz + 1] = st;

        return;
    }

    int mid = (dr + st) >> 1;

    int cate = 0;
    for(int i = st; i <= mid; i ++)
        tmp[i - 1] = 1 - done[i - 1], cate += tmp[i - 1];

    for(int i = mid + 1; i <= dr; i ++)
        tmp[i - 1] = 0;

    int x = 0, y = 1;
    if(cate != 0)
    {
        x = Query(tmp);
        tmp[rez[poz] - 1] = 1;
        y = Query(tmp);
    }

    for(int i = st; i <= dr; i ++)
        tmp[i - 1] = 0;
    tmp[rez[poz] - 1] = 0;

    y == x ? divide(st, mid, poz) : divide(mid + 1, dr, poz);
}

void Solve(int N)
{
    n = N;

    tmp.resize(N);
    rez.resize(N);
	for(int i = 0; i < n; i++)
		tmp[i] = 1;

    if(n == 1)
    {
        rez[0] = 1;
        Answer(rez);
        return;
    }

    for(int i = 0; i < n; i ++)
    {
        tmp[i] = 0;
        int x = Query(tmp);

        if(x == 1)
        {
            done[i] = 1;
            rez[0] = i + 1;
            break;
        }

        tmp[i] = 1;
    }

    //cout << rez[0] << "\n";

    for(int i = 1; i < n; i ++)
    {
        for(int j = 0; j < n; j ++)
            tmp[j] = 0;

        divide(1, n, i - 1);
    }

   /* for(int i = 0; i < n; i ++)
        cout << rez[i] << " ";
    cout << "\n";*/

	Answer(rez);
}

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