Submission #784431

#	Time	Username	Problem	Language	Result	Execution time	Memory
784431		canadavid1	Archery (IOI09_archery)	C++14	21 / 100	2088 ms	5180 KiB

archery

#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x),end(x)
#define both(x) x.first,x.second
signed main()
{
    int N,R,rank;
    cin >> N >> R >> rank;
    vector<int> ranks(2*N-1);
    for(auto &&i : ranks) cin >> i;
    // will eventually have the top half (excluding the best) cycle around, and the worst half (excluding middle)
    // be stationary
    // lower numbers move
    // if rank == 1: any works, return  N
    if(rank == 1) {cout << N << "\n"; exit(0);}



    // just simulate all the positions
    int minend = INT_MAX;
    int position = -1;
    for(int pos = 2*N-2; pos >= 0; pos-=2)
    {
        vector<pair<int,int>> people;
        for(int i = 0; i < 2*N-1;)
        {
            if(i==pos) people.push_back({ranks[i++],rank});
            else people.push_back({ranks[i++],ranks[i++]});
        }
        for(int i = 0; i < R; i++)
        {
            while(i > 4*N && i < R-N) i+=N; // unsure of this bound
            vector<pair<int,int>> people2(people.size());
            people2.back() = {max(both(people[0])),max(both(people.back()))};
            people2[0] = {min(both(people[0])),min(both(people[1]))};
            for(int i = 1; i < people.size()-1; i++)
            {
                people2[i] = {max(both(people[i])),min(both(people[i+1]))};
            }
            people = people2;
        }
        int r = 0; 
        for(; people[r].first!=rank && people[r].second != rank;r++);
        if(r < minend)
        {
            minend = r;
            position = pos/2+1;
        }
    }
    cout << position << "\n";


    // no.2 always moves to pos1, until 1 arrives, then cycles
        // unless it starts with 1, then it waits once first
    // no.3 always moves to pos1, until 2 or 1 arrives, then cycles
        // waits with starting until neither 1 nor 2 is at its position
        // can be complicated if (2 1) (3 ...)
        // as 1 moves up, and 3 comes to 2: (2 3) (...)
        // next, 2 moves up
}

Compilation message (stderr)

archery.cpp: In function 'int main()':
archery.cpp:28:54: warning: operation on 'i' may be undefined [-Wsequence-point]
   28 |             else people.push_back({ranks[i++],ranks[i++]});
      |                                                     ~^~
archery.cpp:36:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             for(int i = 1; i < people.size()-1; i++)
      |                            ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 6
• Subtask 2: 16 / 94