Submission #430815

#	Time	Username	Problem	Language	Result	Execution time	Memory
430815		Amylopectin	Mechanical Doll (IOI18_doll)	C++14	53 / 100	162 ms	26408 KiB

doll

#include <iostream>
#include <stdio.h>
#include <vector>
#include "doll.h"
//#include "grader.cpp"
using namespace std;
const int mxn = 4e5 + 10;
int fr[mxn] = {},to[mxn] = {},tw[mxn] = {},cpoi[mxn] = {},sta[mxn] = {};
vector<int> li[mxn] = {};
void create_circuit(int m, vector<int> a)
{
    int n = a.size(),i,j,po,ru = 1,cru,k;
    vector<int> c(m + 1),x, y;
//    C[0] = -1;
//    for (int i = 1; i <= M; ++i) {
//        C[i] = 1;
//    }
//    for (int k = 0; k < N; ++k) {
//        X[k] = Y[k] = A[k];
//    }
    tw[0] = 1;
    for(i=1; i<20; i++)
    {
        tw[i] = tw[i-1] * 2;
    }
    for(i=0; i<n; i++)
    {
        li[a[i]].push_back(i);
    }
    fr[0] = 0;
    for(i=1; i<=m; i++)
    {
        if(li[i].size() == 0)
        {
            c[i] = 0;
            continue;
        }
        po = 0;
        while(tw[po] < li[i].size())
        {
            po ++;
        }
        if(po == 0)
        {
            fr[li[i][0]] = i;
            to[li[i][0]] = i;
            continue;
        }
        for(j=0; j<li[i].size(); j++)
        {
            to[li[i][j]] = i;
        }
        cru = 0;
        c[i] = -ru;
        cpoi[0] = cru;
        x.push_back(0);
        y.push_back(0);
        for(j=0; j<po-1; j++)
        {
            for(k=0; k<tw[j]; k++)
            {
                x[ru+cpoi[k]-1] = -(ru + cru + 1);
                y[ru+cpoi[k]-1] = -(ru + cru + 2);
                cpoi[k] = cru + 1;
                cpoi[k+tw[j]] = cru + 2;
                x.push_back(0);
                y.push_back(0);
                x.push_back(0);
                y.push_back(0);
                cru += 2;
            }
        }
        for(j=0; j<tw[po-1]; j++)
        {
            fr[li[i][j]] = ru + cpoi[j];
            sta[li[i][j]] = 1;
        }
        for(j=tw[po-1]; j<li[i].size()-1; j++)
        {
            fr[li[i][j]] = ru + cpoi[j-tw[po-1]];
            sta[li[i][j]] = 2;
        }
        for(j=li[i].size()-1; j<tw[po]-1; j++)
        {
            y[ru+cpoi[j-tw[po-1]]-1] = -ru;
        }
        fr[li[i][li[i].size()-1]] = ru + cpoi[tw[po-1]-1];
        sta[li[i][li[i].size()-1]] = 2;
        ru += cru+1;
    }
    c[0] = a[0];
    for(i=0; i<n-1; i++)
    {
        if(sta[i] == 0)
        {
            c[fr[i]] = a[i+1];
        }
        else if(sta[i] == 1)
        {
            x[fr[i]-1] = a[i+1];
        }
        else
        {
            y[fr[i]-1] = a[i+1];
        }
    }
    answer(c, x, y);
}
//int main()
//{
//    cout << "Hello world!" << endl;
//    return 0;
//}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         while(tw[po] < li[i].size())
      |               ~~~~~~~^~~~~~~~~~~~~~
doll.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(j=0; j<li[i].size(); j++)
      |                  ~^~~~~~~~~~~~~
doll.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(j=tw[po-1]; j<li[i].size()-1; j++)
      |                         ~^~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56