oj.uz

Submission #928446

# Submission time Handle Problem Language Result Execution time Memory
928446 2024-02-16T12:01:32 Z aykhn Longest Trip (IOI23_longesttrip) C++17
15 / 100
 34 ms 3548 KB 
#include <bits/stdc++.h>
#include "longesttrip.h"
 
using namespace std;
 
int A[300][300];
map<pair<vector<int>, vector<int>>, int> mp;
 
int ask(vector<int> a, vector<int> b)
{
    if (a.empty() || b.empty()) return 0;
    if (mp.find({a, b}) != mp.end()) return mp[{a, b}];
    return mp[{a, b}] = mp[{b, a}] = are_connected(a, b);
}
 
vector<int> longest_trip(int n, int D)
{
    mp.clear();
    vector<int> v1, v2;
    v1.push_back(0);
    for (int i = 1; i < n; i++)
    {
        if (ask(v1, {i}) && ask(v2, {i})) 
        {
            int id1 = -1, id2 = -1;
            for (int j = 0; j < v1.size(); j++)
            {
                if (ask({v1[j]}, {i}))
                {
                    id1 = j;
                    break;
                }
            }
            for (int j = 0; j < v2.size(); j++)
            {
                if (ask({v2[j]}, {i}))
                {
                    id2 = j;
                    break;
                }
            }
            vector<int> nw;
            for (int j = (id2 + 1) % v2.size(); 1; j = (j + 1) % v2.size())
            {
                nw.push_back(v2[j]);
                if (j == id2) break;
            }
            nw.push_back(i), nw.push_back(v1[id1]);
            for (int j = (id1 + 1) % v1.size(); j != id1; j = (j + 1) % v1.size())
            {
                nw.push_back(v1[j]);
            }
            v2.clear();
            v1 = nw;
        }
        else if (ask(v1, {i})) 
        {
            vector<int> nw;
            if (ask({v1.back()}, {i}))
            {
                nw = v1;
                nw.push_back(i);
            }
            else
            {
                int l = 0, r = (int)v1.size() - 1;
                while (l < r)
                {
                    int mid = (l + r) >> 1;
                    vector<int> x;
                    for (int j = 0; j <= mid; j++)
                    {
                        x.push_back(v1[j]);
                        if (ask(x, {i})) r = mid;
                        else l = mid + 1;
                    }
                }
                int idx = l;
                nw.push_back(i), nw.push_back(v1[idx]);
                for (int j = (idx + 1) % v1.size(); j != idx; j = (j + 1) % v1.size())
                {
                    nw.push_back(v1[j]);
                }
            }
            v1 = nw;
        }
        else if (ask(v2, {i}))
        {
            vector<int> nw;
            if (ask({v2.back()}, {i}))
            {
                nw = v2;
                nw.push_back(i);
            }
            else
            {
                int l = 0, r = (int)v2.size() - 1;
                while (l < r)
                {
                    int mid = (l + r) >> 1;
                    vector<int> x;
                    for (int j = 0; j <= mid; j++)
                    {
                        x.push_back(v2[j]);
                        if (ask(x, {i})) r = mid;
                        else l = mid + 1;
                    }
                }
                int idx = l;
                nw.push_back(i), nw.push_back(v2[idx]);
                for (int j = (idx + 1) % v2.size(); j != idx; j = (j + 1) % v2.size())
                {
                    nw.push_back(v2[j]);
                }
            }
            v2 = nw;
        }
        else v2.push_back(i);
    }
    if (v1.size() > v2.size()) return v1;
    else return v2;
};

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:26:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for (int j = 0; j < v1.size(); j++)
      |                             ~~^~~~~~~~~~~
longesttrip.cpp:34:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             for (int j = 0; j < v2.size(); j++)
      |                             ~~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 34 ms 3548 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 13 ms 600 KB Output is correct
4 Correct 18 ms 1000 KB Output is correct
5 Correct 26 ms 1616 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 14 ms 856 KB Output is correct
4 Correct 17 ms 1156 KB Output is correct
5 Correct 26 ms 948 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Correct 15 ms 704 KB Output is correct
9 Correct 20 ms 1288 KB Output is correct
10 Correct 28 ms 1224 KB Output is correct
11 Correct 28 ms 1880 KB Output is correct
12 Correct 29 ms 1228 KB Output is correct
13 Correct 32 ms 1492 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 16 ms 596 KB Output is correct
4 Correct 18 ms 1008 KB Output is correct
5 Correct 28 ms 1660 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 12 ms 344 KB Output is correct
8 Correct 15 ms 600 KB Output is correct
9 Correct 18 ms 1168 KB Output is correct
10 Correct 29 ms 1208 KB Output is correct
11 Correct 26 ms 984 KB Output is correct
12 Correct 29 ms 1652 KB Output is correct
13 Correct 33 ms 1856 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Incorrect 2 ms 600 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 13 ms 600 KB Output is correct
4 Correct 18 ms 736 KB Output is correct
5 Partially correct 27 ms 1436 KB Output is partially correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 11 ms 344 KB Output is correct
8 Correct 15 ms 656 KB Output is correct
9 Correct 18 ms 1060 KB Output is correct
10 Partially correct 29 ms 1204 KB Output is partially correct
11 Partially correct 27 ms 1956 KB Output is partially correct
12 Partially correct 28 ms 1272 KB Output is partially correct
13 Partially correct 29 ms 1776 KB Output is partially correct
14 Correct 9 ms 344 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Incorrect 2 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -