oj.uz

Submission #823402

# Submission time Handle Problem Language Result Execution time Memory
823402 2023-08-12T13:20:20 Z Dremix10 Mechanical Doll (IOI18_doll) C++17
6 / 100
 1000 ms 12972 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const int N = 3e5+5;
const ll INF = 1e18+5;
const int MOD = 1e9+7;

vector<int> x,y,c;
vector<vector<int> > nxt;

int solve(vector<int> &a){
    assert(!a.empty());
    int n = a.size();
    int i;

    bool ok = 1;
    int curr = a[0];
    vector<int> p1,p2;
    

    for(i=0;i<n-1;i+=2){
        if(curr != a[i] || curr != a[i+1])ok = 0;

        p1.push_back(a[i]);
        p2.push_back(a[i+1]);
    }
    if(curr != a[n-1])ok = 0;

    if(ok){
        return curr;
    }

    if(n%2){
        /// we gotta add
        x.push_back(0);
        y.push_back(0);
        int res = x.size();
        p1.push_back(res*-1);
        p2.push_back(a.back());
        int idx1 = solve(p1);
        cerr<<idx1<<endl;
        x[res-1] = idx1;
        int idx2 = solve(p2);
        y[res-1] = idx2;
        cerr<<idx2<<endl;
        cerr<<res*-1<<": "<<endl;
        cerr<<x[res-1]<<" "<<y[res-1]<<endl;
        for(auto x : p1)cerr<<x<<" ";
        cerr<<endl;
        return res*-1;
    }
    else{
        int idx1 = solve(p1);
        int idx2 = solve(p2);
        x.push_back(idx1);
        y.push_back(idx2);
        int res = x.size();
        cerr<<res*-1<<":"<<endl;
        cerr<<idx1<<" "<<idx2<<endl;
        return res*-1;
    }


}

void create_circuit(int m, vector<int> arr) {
    int n = arr.size();

    c.resize(m+1);

    /// origin goes to first trigger
    c[0] = arr[0];

    int i;
    nxt.assign(m+1,vector<int>());

    for(i=0;i<n;i++){
        if(i < n-1)
            nxt[arr[i]].push_back(arr[i+1]);
        else
            nxt[arr[i]].push_back(0);
    }

    for(i=1;i<=m;i++){
        int cnt = nxt[i].size();

        if(cnt == 0)continue;
        else if(cnt == 1){
            c[i] = nxt[i][0];
        }
        else{
            //int idx = x.size() + 1;

            c[i] = solve(nxt[i]);
        }

    }

    answer(c,x,y);

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 18 ms 6356 KB Output is correct
3 Correct 14 ms 5172 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 3796 KB Output is correct
6 Correct 23 ms 7636 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 18 ms 6356 KB Output is correct
3 Correct 14 ms 5172 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 3796 KB Output is correct
6 Correct 23 ms 7636 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 495 ms 8648 KB Output is correct
9 Correct 345 ms 9472 KB Output is correct
10 Correct 807 ms 12972 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 18 ms 6356 KB Output is correct
3 Correct 14 ms 5172 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 3796 KB Output is correct
6 Correct 23 ms 7636 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 495 ms 8648 KB Output is correct
9 Correct 345 ms 9472 KB Output is correct
10 Correct 807 ms 12972 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Execution timed out 1069 ms 9896 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Correct 11 ms 2860 KB Output is correct
3 Execution timed out 1081 ms 6224 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Correct 11 ms 2860 KB Output is correct
3 Execution timed out 1081 ms 6224 KB Time limit exceeded
4 Halted 0 ms 0 KB -