답안 #731434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
731434	2023-04-27T12:30:39 Z	danikoynov	Sky Walking (IOI19_walk)	C++14	컴파일 오류	0 ms	0 KB

walk

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

void input_file()
{
    freopen("03.in", "r", stdin);
    freopen("03.out", "w", stdout);
}
const int maxn = 1e5 + 10;

struct point
{
    int x, y;

    point(int _x = 0, int _y = 0)
    {
        x = _x;
        y = _y;
    }
};
int n;
point d[maxn];

void print_point(point p)
{
    cout << p.x << " " << p.y << endl;
}

bool cmp(point p1, point p2)
{
    return p1.x < p2.x;
}

int used[maxn], len[maxn], f[maxn], bef[maxn];
vector < int > left_idc;
vector < int > longest_increasing()
{
    int sz = 0;
    len[0] = 0;
    for (int i = 0; i < left_idc.size(); i ++)
    {
        int idx = left_idc[i];
        int lf = 1, rf = sz;
        ///cerr << "-----------" << endl;
        while(lf <= rf)
        {

            int mf = (lf + rf) / 2;
                ///cerr << lf << " : " << rf << " : " << len[mf] << " " << d[idx].y << endl;
            if (len[mf] < d[idx].y)
                lf = mf + 1;
            else
                rf = mf - 1;
        }

        bef[idx] = f[lf - 1];
        f[lf] = idx;
        len[lf] = d[idx].y;
        if (lf > sz)
            sz = lf;
    }


    int idx = f[sz];
    vector < int > sub;
    while(idx != 0)
    {
        ///cerr << idx << endl;
        sub.push_back(idx);
        idx = bef[idx];
    }
    reverse(sub.begin(), sub.end());
    return sub;
}


vector < int > longest_decreasing()
{
    int sz = 0;
    len[0] = 2e9 + 1;
    for (int i = 0; i < left_idc.size(); i ++)
    {
        int idx = left_idc[i];
        int lf = 1, rf = sz;
        ///cerr << "-----------" << endl;
        while(lf <= rf)
        {

            int mf = (lf + rf) / 2;
                ///cerr << lf << " : " << rf << " : " << len[mf] << " " << d[idx].y << endl;
            if (len[mf] > d[idx].y)
                lf = mf + 1;
            else
                rf = mf - 1;
        }

        bef[idx] = f[lf - 1];
        f[lf] = idx;
        len[lf] = d[idx].y;
        if (lf > sz)
            sz = lf;
    }


    int idx = f[sz];
    vector < int > sub;
    while(idx != 0)
    {
        ///cerr << idx << endl;
        sub.push_back(idx);
        idx = bef[idx];
    }
    reverse(sub.begin(), sub.end());
    return sub;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> d[i].x >> d[i].y;
        left_idc.push_back(i);
    }
    sort(d + 1, d + n + 1, cmp);
    for (int i = 1; i <= n; i ++)
        used[i] = 0;

    int cnt = n;
    vector < point > path;

    point st(0, 0);
    int last_step = 0, step = 0;
    vector < int > bef_idc;
    while(left_idc.size() > 0)
    {
        ///cerr << "step " << ++ step << endl;
        cerr << left_idc.size() << endl;
        vector < int > up = longest_increasing();
        vector < int > down = longest_decreasing();
        cerr << "size " << max(up.size(), down.size()) << endl;

        if (up.size() > down.size())
        {
            /**for (int v : up)
                cerr << " " << v;
            cerr << endl;*/
            last_step = 1;
            st.x = d[up[0]].x;
             path.push_back(st);
            if (st.y > d[up[0]].y)
            {
                st.y = d[up[0]].y;
                path.push_back(st);
            }

            for (int i = 0; i < up.size(); i ++)
            {
                point cur = d[up[i]];
                if (i % 2 == 0)
                {
                    st.y = cur.y;
                    if (i + 1 != up.size())
                        st.y = d[up[i + 1]].y;
                    path.push_back(st);
                }
                else
                {
                    st.x = cur.x;
                    if (i + 1 != up.size())
                        st.x = d[up[i + 1]].x;
                    path.push_back(st);
                }
            }

            unordered_set < int > st;
            for (int v : up)
                st.insert(v);
                      ///cerr << "type increasing " << st.size() << " : " << left_idc.size() << endl;
                      /**for (int v : st)
                        cerr << v << " ";
                      cerr << endl;
                      for (int v : left_idc)
                        cerr << v << " ";
                      cerr << endl;*/
                ///cerr << st.size() << endl;

            vector < int > new_idc;
            for (int v : left_idc)
                if (st.find(v) == st.end())
                new_idc.push_back(v);
            left_idc = new_idc;
        }
        else
        {
            last_step = 0;
            st.y = d[down[0]].y;
            path.push_back(st);
            if (st.x > d[down[0]].x)
            {
                st.x = d[down[0]].x;
                path.push_back(st);
            }
            for (int i = 0; i < down.size(); i ++)
            {
                point cur = d[down[i]];
                if (i % 2 == 1)
                {
                    st.y = cur.y;
                    if (i + 1 != down.size())
                        st.y = d[down[i + 1]].y;
                    path.push_back(st);
                }
                else
                {
                    st.x = cur.x;
                    if (i + 1 != down.size())
                        st.x = d[down[i + 1]].x;
                    path.push_back(st);
                }
            }


            unordered_set < int > st;
            for (int v : down)
                st.insert(v);
                //cerr << "type decreasing " << st.size() << " : " << left_idc.size() << endl;
            vector < int > new_idc;
            for (int v : left_idc)
                if (st.find(v) == st.end())
                new_idc.push_back(v);
            left_idc = new_idc;

        }
        ///
    }

    cerr << path.size() << endl;
    cout << path.size() << endl;
    for (point cur : path)
        print_point(cur);

}

void all_cases(int to)
{
    for (int cs = 4; cs <= 4; cs ++)
    {
        string file_name_in, file_name_out;
                    file_name_in = (char)(cs + '0');
                    file_name_in = file_name_in + ".in";
            file_name_out = (char)(cs + '0');
            file_name_out = file_name_out + ".out.txt";

            file_name_in = "0" + file_name_in;
            file_name_out = "0" + file_name_out;
        if (cs == 10)
        {
            file_name_in = "10.in";
            file_name_out = "10.out.txt";
        }
        cerr << "Test: " << cs << endl;
        freopen(file_name_in.c_str(), "r", stdin);
        freopen(file_name_out.c_str(), "w", stdout);

        solve();

    }
}
int main()
{
    all_cases(1);
    return 0;
}

Compilation message

walk.cpp: In function 'std::vector<int> longest_increasing()':
walk.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < left_idc.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'std::vector<int> longest_decreasing()':
walk.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 0; i < left_idc.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'void solve()':
walk.cpp:157:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |             for (int i = 0; i < up.size(); i ++)
      |                             ~~^~~~~~~~~~~
walk.cpp:163:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |                     if (i + 1 != up.size())
      |                         ~~~~~~^~~~~~~~~~~~
walk.cpp:170:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |                     if (i + 1 != up.size())
      |                         ~~~~~~^~~~~~~~~~~~
walk.cpp:204:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |             for (int i = 0; i < down.size(); i ++)
      |                             ~~^~~~~~~~~~~~~
walk.cpp:210:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |                     if (i + 1 != down.size())
      |                         ~~~~~~^~~~~~~~~~~~~~
walk.cpp:217:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |                     if (i + 1 != down.size())
      |                         ~~~~~~^~~~~~~~~~~~~~
walk.cpp:129:9: warning: unused variable 'cnt' [-Wunused-variable]
  129 |     int cnt = n;
      |         ^~~
walk.cpp:133:9: warning: variable 'last_step' set but not used [-Wunused-but-set-variable]
  133 |     int last_step = 0, step = 0;
      |         ^~~~~~~~~
walk.cpp:133:24: warning: unused variable 'step' [-Wunused-variable]
  133 |     int last_step = 0, step = 0;
      |                        ^~~~
walk.cpp: In function 'void input_file()':
walk.cpp:7:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     freopen("03.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
walk.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen("03.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
walk.cpp: In function 'void all_cases(int)':
walk.cpp:263:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  263 |         freopen(file_name_in.c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
walk.cpp:264:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  264 |         freopen(file_name_out.c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccBsudZe.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccWG2Rwe.o:walk.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccBsudZe.o: in function `main':
grader.cpp:(.text.startup+0x385): undefined reference to `min_distance(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)'
collect2: error: ld returned 1 exit status