Submission #1332255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1332255		hauserl	A String Problem (EGOI25_stringproblem)	C++20	0 / 100	13 ms	2748 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 = 1;
    vector<int> counts(TN,0); // axis


    for (int i = 0; i < TN; i++) {
        // ein pin gerade einer ungerade -> sonst falsch
        int P1 = strings[i].f;
        int P2 = strings[i].s;
        if ((P1+P2)%2 != 1) continue;

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

        if (axis%2 != 1) continue;

        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);
    vector<bool> donePin(2*N);

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

        if (doneString[string] || donePin[i]) continue;


        doneString[string] = true;
        
        // int second = (((bAxis + 1) % TN - (i - bAxis)) + TN) % TN;
        int second = (bAxis - i + 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 - (prevSecond - bAxis)) + TN) % TN;
        int oppositePrevSecond = (bAxis - prevSecond + TN) %TN;
        
        int string2 = circle[oppositePrevSecond];

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

            second = prevSecond;

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

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

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

            
            // oppositePrevSecond = (((bAxis + 1) % TN - (prevSecond - bAxis)) + TN) % TN;
            oppositePrevSecond = (bAxis - prevSecond + TN) %TN;
            if (oppositePrevSecond == prevSecond) oppositePrevSecond++;
            oppositePrevSecond %= 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;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:106: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=]
  106 |     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: 0 / 16
• Subtask 4: 0 / 12
• Subtask 5: 0 / 28
• Subtask 6: 0 / 30