oj.uz

Submission #416358

# Submission time Handle Problem Language Result Execution time Memory
416358 2021-06-02T10:36:28 Z model_code Diamond Hands (innopolis2021_final_B) Java 11
28 / 100
 435 ms 174112 KB 
import java.io.*;
import java.util.*;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Polyline solver = new Polyline();
        solver.solve(1, in, out);
        out.close();
    }

    static class Polyline {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            int MAX = 2000;
            int INF = Integer.MAX_VALUE / 2;
            int[] hasY = new int[MAX + 1];
            Arrays.fill(hasY, INF);
            hasY[0] = 0;
            int lastX = -1;
            for (int i = 0; i <n; i++) {
                int x = in.nextInt();
                hasY[x] = in.nextInt();
                if (i + 1 == n) {
                    lastX = x;
                }
            }
            int[][][] dp = new int[2][lastX + 1][2 * MAX + 1];
            int[][][] pr = new int[2][lastX + 1][2 * MAX + 1];
            for (int[][] i : dp) {
                for (int[] j : i) {
                    Arrays.fill(j, INF);
                }
            }
            dp[0][0][0 + MAX] = dp[1][0][0 + MAX] = 0;
            for (int x = 0; x < lastX; x++) {
                int startY = -MAX, endY = MAX;
                if (hasY[x] != INF) {
                    startY = endY = hasY[x];
                }
                for (int y = startY; y <= endY; y++) {
                    for (int d = 0; d < 2; d++) {
                        int val = dp[d][x][y + MAX];
                        if (val != INF) {
                            for (int newD = 0; newD < 2; newD++) {
                                int newVal = val + ((d == newD) ? 0 : 1);
                                if (dp[newD][x + 1][y + MAX + (2 * newD - 1)] > newVal) {
                                    dp[newD][x + 1][y + MAX + (2 * newD - 1)] = newVal;
                                    pr[newD][x + 1][y + MAX + (2 * newD - 1)] = d;
                                }
                            }
                        }
                    }
                }
            }
            int bestD = dp[0][lastX][hasY[lastX] + MAX] < dp[1][lastX][hasY[lastX] + MAX] ? 0 : 1;
            if (dp[bestD][lastX][hasY[lastX] + MAX] == INF) {
                out.println(-1);
            } else {
                List<Integer> ls = new ArrayList<>();
                List<Character> cs = new ArrayList<>();
                int curY = hasY[lastX], curD = bestD;
                for (int curX = lastX; curX > 0; curX--) {
                    int prevD = pr[curD][curX][curY + MAX];
                    char c = curD == 1 ? '+' : '-';
                    if (cs.size() > 0 && cs.get(cs.size() - 1) == c) {
                        ls.set(ls.size() - 1, ls.get(ls.size() - 1) + 1);
                    } else {
                        ls.add(1);
                        cs.add(c);
                    }
                    curY -= 2 * curD - 1;
                    curD = prevD;
                }
                out.println(ls.size());
                for (int i = ls.size() - 1; i >= 0; i--) {
                    out.println(ls.get(i) + " " + cs.get(i));
                }
            }
        }

    }

    static class FastScanner {
        public BufferedReader br;
        public StringTokenizer st;

        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }

        public FastScanner(String fileName) {
            try {
                br = new BufferedReader(new FileReader(fileName));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                String line = null;
                try {
                    line = br.readLine();
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (line == null) {
                    throw new UnknownError();
                }
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }

    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 12144 KB OK, n=2 ans=1
2 Correct 171 ms 12052 KB OK, n=3 ans=1
3 Correct 148 ms 10468 KB OK, n=1 ans=1
4 Correct 195 ms 14448 KB OK, n=5 ans=1
5 Correct 175 ms 14532 KB OK, n=8 ans=1
6 Correct 318 ms 106468 KB OK, n=88 ans=1
7 Runtime error 80 ms 8300 KB Execution failed because the return code was nonzero
8 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 12144 KB OK, n=2 ans=1
2 Correct 171 ms 12052 KB OK, n=3 ans=1
3 Correct 148 ms 10468 KB OK, n=1 ans=1
4 Correct 195 ms 14448 KB OK, n=5 ans=1
5 Correct 175 ms 14532 KB OK, n=8 ans=1
6 Correct 318 ms 106468 KB OK, n=88 ans=1
7 Runtime error 80 ms 8300 KB Execution failed because the return code was nonzero
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 12144 KB OK, n=2 ans=1
2 Correct 171 ms 12052 KB OK, n=3 ans=1
3 Correct 148 ms 10468 KB OK, n=1 ans=1
4 Correct 195 ms 14448 KB OK, n=5 ans=1
5 Correct 175 ms 14532 KB OK, n=8 ans=1
6 Correct 318 ms 106468 KB OK, n=88 ans=1
7 Runtime error 80 ms 8300 KB Execution failed because the return code was nonzero
8 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 12132 KB OK, n=5 ans=3
2 Correct 212 ms 13636 KB OK, n=10 ans=4
3 Correct 205 ms 16344 KB OK, n=20 ans=5
4 Correct 207 ms 19180 KB OK, n=50 ans=9
5 Correct 201 ms 24620 KB OK, n=100 ans=18
6 Correct 381 ms 173292 KB OK, n=200 ans=46
7 Correct 285 ms 83116 KB OK, n=100 ans=5
8 Correct 360 ms 173216 KB OK, n=200 ans=20
9 Correct 369 ms 174112 KB OK, n=400 ans=76
10 Correct 362 ms 171428 KB OK, n=1000 ans=196
11 Correct 383 ms 171536 KB OK, n=1000 ans=434
12 Correct 375 ms 170760 KB OK, n=1000 ans=582
13 Correct 379 ms 170844 KB OK, n=1000 ans=798
14 Correct 395 ms 171584 KB OK, n=1000 ans=867
15 Correct 386 ms 166988 KB OK, n=2000 ans=200
16 Correct 400 ms 166988 KB OK, n=1998 ans=500
17 Correct 396 ms 167012 KB OK, n=2000 ans=800
18 Correct 398 ms 167100 KB OK, n=1995 ans=1000
19 Correct 435 ms 166824 KB OK, n=2000 ans=1500
20 Correct 389 ms 165996 KB OK, n=2000 ans=2000
21 Correct 108 ms 13612 KB OK, no solution, n=10
22 Correct 134 ms 28440 KB OK, no solution, n=50
23 Correct 299 ms 173332 KB OK, no solution, n=400
24 Correct 304 ms 170804 KB OK, no solution, n=1000
25 Correct 326 ms 166092 KB OK, no solution, n=2000
26 Correct 327 ms 166192 KB OK, no solution, n=2000
27 Correct 176 ms 12340 KB OK, n=4 ans=5
28 Correct 191 ms 24168 KB OK, n=30 ans=31
29 Correct 378 ms 173416 KB OK, n=500 ans=501
30 Correct 395 ms 171688 KB OK, n=1000 ans=1001

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 12144 KB OK, n=2 ans=1
2 Correct 171 ms 12052 KB OK, n=3 ans=1
3 Correct 148 ms 10468 KB OK, n=1 ans=1
4 Correct 195 ms 14448 KB OK, n=5 ans=1
5 Correct 175 ms 14532 KB OK, n=8 ans=1
6 Correct 318 ms 106468 KB OK, n=88 ans=1
7 Runtime error 80 ms 8300 KB Execution failed because the return code was nonzero
8 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 12144 KB OK, n=2 ans=1
2 Correct 171 ms 12052 KB OK, n=3 ans=1
3 Correct 148 ms 10468 KB OK, n=1 ans=1
4 Correct 195 ms 14448 KB OK, n=5 ans=1
5 Correct 175 ms 14532 KB OK, n=8 ans=1
6 Correct 318 ms 106468 KB OK, n=88 ans=1
7 Runtime error 80 ms 8300 KB Execution failed because the return code was nonzero
8 Halted 0 ms 0 KB -