oj.uz

Submission #963895

# Submission time Handle Problem Language Result Execution time Memory
963895 2024-04-16T02:07:10 Z steveonalex Rail (IOI14_rail) C++17
100 / 100
 126 ms 1432 KB 
#include <bits/stdc++.h>
#include "rail.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }
 
// int getDistance(int i, int j){
//     cout << "? " << i << " " << j << endl;
//     int verdict; cin >> verdict;
//     return verdict;
// }
 
void findLocation(int n, int first, int location[], int stype[]){
    for(int i = 0; i<n; ++i) location[i] = stype[i] = 0;
    location[0] = first; stype[0] = 1;
 
    vector<int> from0(n);
    for(int i = 1; i<n; ++i){
        from0[i] = getDistance(0, i);
    }
 
    vector<int> sigma(n);
    for(int i= 0; i<n; ++i) sigma[i] = i;
 
    sort(ALL(sigma), [&from0](int x, int y){return from0[x] < from0[y];});
 
    int l = -1, r = -1;
    stype[0] = 1; stype[sigma[1]] = 2;
    location[0] = first, location[sigma[1]] = first + from0[sigma[1]];
 
    printArr(sigma, " ", "\n", cerr);
 
    map<int, int> mp;
    mp[location[0]] = 0;
    mp[location[sigma[1]]] = sigma[1];
 
    set<int> down; down.insert(location[0]);
    set<int> up; up.insert(location[sigma[1]]);
    for(int i: sigma){
        if (i == 0 || i == sigma[1]) continue;
        cerr << "cur: " << i << "\n";
        int x = getDistance(sigma[1], i);
        if (x + from0[sigma[1]] != from0[i]){ // to the right of 1
            cerr << "right\n";
            if (r == -1){
                location[i] = location[0] + from0[i];
                stype[i] = 2;
                r = i;
            }
            else{
                int y = getDistance(r, i);
                int pos = *up.upper_bound(location[r] - y);
                int z = mp[pos];
                if (from0[z] + y - abs(from0[r] - from0[z]) == from0[i]){
                    location[i] = location[r] - y;
                    stype[i] = 1;
                }
                else{
                    location[i] = location[0] + from0[i];
                    stype[i] = 2;
                    r = i;
                }
            }
        }
        else{ // to the left of 1
            cerr << "left\n";
            if (x < from0[sigma[1]]){
                location[i] = location[sigma[1]] - x;
                stype[i] = 1;
            }
            else if (l == -1){
                location[i] = location[sigma[1]] - x;
                stype[i] = 1;
                l = i;
            }
            else{
                int y = getDistance(l, i);
                int pos = *(--down.upper_bound(location[l] + y));
                int z = mp[pos];
                // cerr << y << " " << pos << " " << location[l] << " " << from0[z] << "\n";
                if (from0[z] + y - abs(from0[l] - from0[z]) == from0[i]){
                    location[i] = location[l] + y;
                    stype[i] = 2;
                }
                else{
                    location[i] = location[0] - from0[i] + from0[sigma[1]] * 2;
                    stype[i] = 1;
                    l = i;
                }
            }
 
        }
        mp[location[i]] = i;
        if (stype[i] == 1) down.insert(location[i]);
        else up.insert(location[i]);
        cerr << stype[i] << " " << location[i] << "\n";
    }
 
}
 
 
// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
//     int n = 4;
//     int location[n], stype[n];
//     findLocation(n, 3, location, stype);
//     for(int i = 0; i<n; ++i) cout << location[i] << " " << stype[i] << "\n";
 
//     return 0;
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 344 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 2 ms 540 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 1168 KB Output is correct
2 Correct 106 ms 1112 KB Output is correct
3 Correct 106 ms 1052 KB Output is correct
4 Correct 105 ms 1176 KB Output is correct
5 Correct 105 ms 1196 KB Output is correct
6 Correct 104 ms 1148 KB Output is correct
7 Correct 106 ms 1124 KB Output is correct
8 Correct 105 ms 1108 KB Output is correct
9 Correct 113 ms 1204 KB Output is correct
10 Correct 105 ms 1184 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 1156 KB Output is correct
2 Correct 105 ms 1108 KB Output is correct
3 Correct 105 ms 1148 KB Output is correct
4 Correct 105 ms 1108 KB Output is correct
5 Correct 111 ms 1168 KB Output is correct
6 Correct 105 ms 1148 KB Output is correct
7 Correct 109 ms 1196 KB Output is correct
8 Correct 105 ms 1108 KB Output is correct
9 Correct 113 ms 1152 KB Output is correct
10 Correct 104 ms 1108 KB Output is correct
11 Correct 105 ms 1108 KB Output is correct
12 Correct 107 ms 1220 KB Output is correct
13 Correct 114 ms 1408 KB Output is correct
14 Correct 126 ms 1172 KB Output is correct
15 Correct 106 ms 1112 KB Output is correct
16 Correct 104 ms 1104 KB Output is correct
17 Correct 106 ms 1432 KB Output is correct
18 Correct 106 ms 1104 KB Output is correct
19 Correct 108 ms 1316 KB Output is correct
20 Correct 104 ms 1104 KB Output is correct