제출 #1332244

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1332244		hauserl	A String Problem (EGOI25_stringproblem)	C++20	8 / 100	15 ms	2236 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;

int main() {

    int N; scanf("%d",&N);
    int TN = N*2;

    vector<pair<int, int>> strings(N);
    vector<int> circle(2*N);

    for (int i = 0; i < N; i++) {
        int a,b; scanf("%d %d",&a, &b);
        strings[i] = {a,b};
        circle[a] = i;
        circle[b] = i;
    }

    int maxParallelCount = INT_MIN;
    int bAxis = 0;
    vector<int> counts(N,0); // axis


    for (int i = 0; i < N; i++) { // iterate over strings
        // ein pin gerade einer ungerade -> sont falsch
        int P1 = strings[i].f;
        int P2 = strings[i].s;

        if ((P1+P2)%2 != 1) continue;

        // int axis = (P1 + P2) % N - 1; // etwas ist perpenticular zu einer achse die die summe aus den pins ist mod N 1-2 0-3 - 9-4 -> 3

        // int axis = 0;
        int axis = ((min(P1, P2) + (max(P1, P2) - min(P1, P2))/2)) % N;
        // int mindist = min((P1 - P2 + TN) % TN, (P2 - P1 + TN) % TN) / 2;

        // if ((min(P1, P2) + 2*mindist + 1) % TN == max(P1, P2)) {
        //     axis = min(P1, P2) + mindist;
        // } else {
        //     axis = min(P1, P2) - mindist + TN;
        // }

        axis %= N;

        // min aus den 2 distanzen -> / 2 -> + oder - den richtigen wert // if ((min + 2*d) %N  == max) -> zu min addieren | else -> von min subtrahieren
        counts[axis]++;

        if (counts[axis] > maxParallelCount) {
            maxParallelCount = counts[axis];
            bAxis = axis;
        }
    }


    // immer irgendwo bei nicht parallelen anfangen und die lücke die entsteht mit dem gegenüber füllen
    vector<tuple<int, int, int>> moves;
    vector<bool> doneString(N); // strings done
    vector<bool> donePin(2*N);
    // vector<int> filler;

    for (int i = 0; i < 2*N; i++) {
        int string = circle[i];

        if (doneString[string]) continue;

        if (donePin[i]) {
            // filler.push_back(string);
        } else {

            // fix first
            doneString[string] = true;
            // int second = (((bAxis - 1 + TN) % TN - (i - bAxis)) + TN) % TN;
            int second = (((bAxis + 1) % TN - (i - bAxis)) + TN) % TN;
            int prevSecond = strings[string].f == i ? strings[string].s : strings[string].f;

            if (second == prevSecond) {
                doneString[string] = true;
                donePin[i] = true;
                donePin[second] = true;
                continue;
            }

            moves.push_back({string, prevSecond, second});

            donePin[i] = true;
            donePin[second] = true;


            // int oppositePrevSecond = (((bAxis - 1 + TN) % TN - (prevSecond - bAxis)) + TN) % TN;
            int oppositePrevSecond = (((bAxis + 1) % TN - (prevSecond - bAxis)) + TN) % TN;
            int string2 = circle[oppositePrevSecond];

            while (!doneString[string2]) {
                doneString[string2]= true;

                second = prevSecond;

                prevSecond = strings[string2].f == oppositePrevSecond ? strings[string2].s : strings[string].f;

                moves.push_back({string2, prevSecond, second});

                donePin[second] = true;
                donePin[oppositePrevSecond] = true;

                
                // int oppositePrevSecond = (((bAxis - 1 + TN) % TN - (prevSecond - bAxis)) + TN) % TN;
            int oppositePrevSecond = (((bAxis + 1) % TN - (prevSecond - bAxis)) + TN) % TN;
                string2 = circle[oppositePrevSecond];
            }
        }        
    }


    printf("%d\n", moves.size());
    for (int i = 0; i < moves.size(); i++) {
        printf("%d %d %d\n", get<0>(moves[i]), get<1>(moves[i]), get<2>(moves[i]));
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:117:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
  117 |     printf("%d\n", moves.size());
      |             ~^     ~~~~~~~~~~~~
      |              |               |
      |              int             std::vector<std::tuple<int, int, int> >::size_type {aka long unsigned int}
      |             %ld
Main.cpp:9:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     int N; scanf("%d",&N);
      |            ~~~~~^~~~~~~~~
Main.cpp:16:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         int a,b; scanf("%d %d",&a, &b);
      |                  ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 14
• Subtask 3: 8 / 16
• Subtask 4: 0 / 12
• Subtask 5: 0 / 28
• Subtask 6: 0 / 30